In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set @math of @math (weighted) uncertain points in the plane and each uncertain point has @math possible locations each associated with a probability for the point appearing at that location. The goal is to find a point @math in the plane which minimizes the maximum expected rectilinear distance from @math to all uncertain points of @math , and @math is called a rectilinear center. We present an algorithm that solves the problem in @math time. Since the input size of the problem is @math , our algorithm is optimal.
The problem of finding one-center among uncertain points on a line has been considered in our previous work @cite_11 , where an @math time algorithm was given. An algorithm for computing @math centers for general @math was also given in @cite_11 with the running time @math . In fact, in @cite_11 we considered the @math -center problem under a more general uncertain model where each uncertain point can appear in @math intervals. We also studied the one-center problem for uncertain points on tree networks in @cite_2 , where a linear-time algorithm was proposed.
@cite_2 @cite_11
2401996954 1628490320
Uncertain data has been very common in many applications. In this paper, we consider the one-center problem for uncertain data on tree networks. In this problem, we are given a tree T and n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to find a point (x^* ) on T such that the maximum (weighted) expected distance from (x^* ) to all uncertain points is minimized. To the best of our knowledge, this problem has not been studied before. We propose a refined prune-and-search technique that solves the problem in linear time. Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k-center problem on one-dimensional uncertain data. The input is a set P of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (i.e., a histogram). The goal is to find a set Q of k points on the line to minimize the maximum expected distance from the uncertain points of P to their expected closest points in Q. We present efficient algorithms for this uncertain k-center problem and their running times almost match those for the "deterministic" k-center problem.