In this paper, 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 appear 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 @math . The problem has not been studied before. We present an O(|T|+M ^2 M) time algorithm for the problem, 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. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.
As mentioned above, the deterministic'' version of the center-coverage problem is solvable in linear time @cite_19 , where all demand points are on the vertices. For the @math -center problem, Megiddo and Tamir @cite_12 presented an @math time algorithm ( @math is the size of the tree), which was improved to @math time by Cole @cite_21 . The unweighted case was solved in linear time by Frederickson @cite_11 .
@cite_19 @cite_21 @cite_12 @cite_11
2964179137 2046812523 1988777116 1529668588
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 ). Abstract This paper considers the planar Euclidean two-center problem: given a planar n-point set S, find two congruent circular disks of the smallest radius covering S. The main result is a deterministic algorithm with running time O(nlog2nlog2logn), improving the previous O(nlog9n) bound of Sharir and almost matching the randomized O(nlog2n) bound of Eppstein. If a point in the intersection of the two disks is given, then we can solve the problem in O(nlogn) time with high probability. In this paper, we study the problem of moving @math n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an @math O(n2logn) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes @math O(n2) time. We present an @math O(nlogn) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes @math O(n) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in @math O(n) time, improving the previously best @math O(n2) time solution. Linear-time and -space algorithms are presented for solving three versions of the p-center problem in a tree. The techniques are an application of parametric search.