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.
Some coverage problems in various geometric settings have also been studied. For example, the unit disk coverage problem is to compute a minimum number of unit disks to cover a given set of points in the plane. The problem is NP-hard and a polynomial-time approximation scheme was known @cite_38 . The discrete case where the disks must be selected from a given set was also studied @cite_30 . See @cite_25 @cite_14 @cite_40 @cite_2 and the references therein for various problems of covering points using squares. Refer to a survey @cite_10 for more geometric coverage problems.
@cite_30 @cite_38 @cite_14 @cite_40 @cite_2 @cite_10 @cite_25
2054505111 2100961486 2144614313 1981309786 2024500486
We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P=NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in Re3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local search algorithm which iterates over local improvements only. A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error e > O, with running time that is polynomial when e is fixed. Though the polynomiality of these algorithms depends on the degree of approximation e being fixed, they cannot be improved, owing to a negative result stating that there are no fully polynomial approximation schemes for strongly NP-complete problems unless NP = P. The unified technique that is introduced here, referred to as the shifting strategy, is applicable to numerous geometric covering and packing problems. The method of using the technique and how it varies with problem parameters are illustrated. A similar technique, independently devised by B. S. Baker, was shown to be applicable for covering and packing problems on planar graphs. We study a geometric version of the Red-Blue Set Cover problem originally proposed by (2000) 1: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares. Let P = p1, p2,…,pn be a set of points in d-space. We study the problem of covering with the minimum number of fixed-size orthogonal hypersquares (CSd for short) all points in P. We present a fast approximation algorithm that generates provably good solutions and an improved polynomial-time approximation scheme for this problem. A variation of the CSd problem is the CRd problem, covering by fixed-size orthogonal hyperrectangles, where the covering of the points is by hyperrectangles with dimensions D1, D2,…,Dd instead of hypersquares of size D. Another variation is the CDd problem, where we cover the set of points with hyperdiscs of diameter D. Our algorithms can be easily adapted to these problems. Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one rectangle is restricted to be axis-parallel but the other rectangle is allowed to be reoriented freely. For both of the problems, we present O(n2log n)-time algorithms using O(n) space.