Computing the Rectilinear Center of Uncertain Points in the Plane.

In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set 𝒫 of n (weighted) uncertain points in the plane and each uncertain point has m possible locations each associated with a probability for the point appearing at that location. The goal is to find a point q ∗ in the plane which minimizes the maximum expected rectilinear distance from q ∗ to all uncertain points of 𝒫 , and q ∗ is called a rectilinear center. We present an algorithm that solves the problem in O (m n) time. Since the input size of the problem is Θ (m n) , our algorithm is optimal. [ABSTRACT FROM AUTHOR]