Computing the Rectilinear Center of Uncertain Points in the Plane

Haitao Wang, Jingru Zhang

Abstract

This paper presents an optimal $O(mn)$ time algorithm for the rectilinear one-center problem involving $n$ uncertain points, each defined by $m$ discrete possible locations. By employing a sophisticated nested prune-and-search technique, the authors overcome the $O(nm^2)$ complexity inherent in naive approaches. This result matches the theoretical lower bound for the problem, providing a highly efficient solution for facility location under spatial uncertainty.

Introduction

In many real-world applications, such as emergency service planning or logistics, the exact locations of target points are often uncertain due to sensor noise or sampling errors. This paper addresses the rectilinear one-center problem for uncertain points. Given $n$ uncertain points $P_i$, where each $P_i$ can be at one of $m$ discrete locations with specific probabilities, the goal is to find a center $q^*$ that minimizes the maximum expected rectilinear (Manhattan) distance to any point $P_i$.

Geometric Framework

The fundamental challenge lies in the nature of the objective function. For each uncertain point $P_i$, the expected rectilinear distance function $Ed_i(x, y)$ is a convex piecewise linear function. The rectilinear center is the point that minimizes the upper envelope of these $n$ functions.

Figure 1: The expected rectilinear distance function $Ed_i(x,y)$ for an uncertain point $P_i$ with discrete locations $p_{i1}, \dots, p_{i4}$.

As shown in Figure 1, the function $Ed_i(x, y)$ forms a "bowl-shaped" surface. The complexity arises because this surface is composed of $O(m^2)$ linear patches defined by a grid of the $x$ and $y$ coordinates of the $m$ possible locations. A standard 3D linear programming approach would result in $O(nm^2)$ time, which is suboptimal.

The Nested Prune-and-Search Algorithm

To achieve optimality, the authors developed a nested prune-and-search algorithm. This technique avoids explicit construction of the $O(nm^2)$ patches by iteratively shrinking the search space.

1. Decision Algorithm

A critical component is the decision algorithm. Given a line in the plane, this routine determines which side of the line contains the optimal center $q^*$. The authors optimized this to run in time proportional to the number of grid lines currently intersecting the search region, rather than the total number of locations.

2. Pruning Strategy

The algorithm uses a two-tier recursion:

  • Outer Recursion: Focuses on pruning the number of uncertain points ($n$).
  • Inner Recursion: Focuses on pruning the coordinate values ($m$) that define the grid for each point.

By shrinking a bounding box $R$ until it no longer intersects the grid lines of a significant portion of the points, the complex piecewise functions simplify into single linear planes within $R$. These simplified points can then be pruned, reducing the problem size.

Key Results and Extensions

The primary result is an optimal $O(mn)$ time complexity algorithm. Because the input size is $\Theta(mn)$, this is the fastest possible asymptotic bound.

The method is robust and extends to several related problems:

  • Weighted Centers: The algorithm handles weighted points without increasing complexity.
  • $L_\infty$ Metric: Due to the relationship between $L_1$ and $L_\infty$ metrics (a 45-degree rotation), the algorithm also solves the $L_\infty$ one-center problem in $O(mn)$ time.

Conclusion

This work provides a definitive algorithmic solution for the rectilinear one-center problem under discrete uncertainty. While the Euclidean ($L_2$) version remains significantly more complex due to the lack of exact algebraic solutions (the Weber problem), this $O(mn)$ approach sets a benchmark for rectilinear facility location. Future research may explore extending these pruning techniques to higher dimensions or multi-center ($k$-center) problems.

Summary updated

BibTeX
@article{wang2018computing,
  author = {Haitao Wang and Jingru Zhang},
  title = {{Computing the Rectilinear Center of Uncertain Points in the Plane}},
  journal = {Int. J. Comput. Geom. Appl.},
  year = {2018},
  doi = {10.1142/s0218195918500073},
}
Figure