2017/04/24 by Haitao Wang, Wang, Haitao, Jingru Zhang +1
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1704.07497
A preliminary version will appear in WADS 2017
arxiv created 2017/04/24 · arxiv updated 2017/04/26
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 Pi∈ P is uncertain but is known to appear in one of mi 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 Pi∈ P, the expected distance from Pi to at least one center is no more than λ. The problem has not been studied before. We present an O(|T|+Mlog2 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=∑Pi∈ Pmi. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.