Computing the Rectilinear Center of Uncertain Points in the Plane
Haitao Wang, Jingru Zhang · International Journal of Computational Geometry & Applications · 2018
In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set [Formula: see text] of [Formula: see text] (weighted) uncertain points in the plane and each uncertain point has [Formula: see text] possible locations each associated with a probability for the point appearing at that location. The goal is to find a point [Formula: see text] in the plane which minimizes the maximum expected rectilinear distance from [Formula: see text] to all uncertain points of [Formula: see text], and [Formula: see text] is called a rectilinear center. We present an algorithm that solves the problem in [Formula: see text] time. Since the input size of the problem is [Formula: see text], our algorithm is optimal.