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
2964179137 2345659331 2401996954 2303014626
We consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set ( P ) of n (weighted) demand points, and the location of each demand point (P_i P ) is uncertain but is known to be in one of (m_i ) points on T each associated with a probability. Given a covering range ( ), the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point (P_i P ), the expected distance from (P_i ) to at least one center is no more than ( ). The problem has not been studied before. We present an (O(|T|+M ^2 M) ) time algorithm, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of ( P ), i.e., (M= _ P_i P m_i ). 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 @math xź on T such that the maximum (weighted) expected distance from @math 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. 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. We consider the one-dimensional one-center problem on uncertain data. We are given a set P of n (weighted) uncertain points on a real line L and each uncertain point is specified by a probability density function that is a piecewise-uniform function (i.e., a histogram). The goal is to find a point c (the center) on L such that the maximum expected distance from c to all uncertain points of P is minimized. We present a linear-time algorithm for this problem.