Abstract
Geometric Covering and Packing problems have been extensively studied in the last few decades and have applications in diverse areas. Several variants and generalizations of these problems have been studied recently. In this paper, we look at the following covering variants where we require that each point is “uniquely” covered, i.e., it is covered by exactly one object: Unique Coverage problem, where we want to maximize the number of uniquely covered points and Exact Cover problem, where we want to uniquely cover every point and minimize the number of objects used for covering. We also look at the following generalizations: Multi Cover problem, a generalization of Set Cover, the objective is to select the minimum subset of objects with the constraint that each input point p is covered by at least \(d_p\) objects in the solution, where \(d_p\) is the demand of point p. And Shallow Packing problem, a generalization of Packing problem, where we want to select the maximum subset of objects with the constraint that any point in the plane is contained in at most k objects in the solution. The above problems are NP-hard even for unit squares in the plane. Thus, the focus has been on obtaining good approximation algorithms. Local search has been quite successful in the recent past in obtaining good approximation algorithms for a wide variety of problems. We consider the Unique Coverage and Multi Cover problems on non-piercing objects, which is a broad class that includes squares, disks, pseudo-disks, etc. and show that the local search algorithm yields a PTAS approximation under the assumption that the depth of every input point is at most some fixed constant. For Unique Coverage we further assume that every object has at most a constant degree. For the Shallow Packing problem, we show that the local search algorithm yields a PTAS approximation for objects with sub-quadratic union complexity, which is a very broad class of objects that even includes non-piercing objects. For the Exact Cover problem, we show that finding a feasible solution is NP-hard even for unit squares in the plane, thus negating the existence of polynomial time approximation algorithms.
Similar content being viewed by others
Notes
A set of regions is said to be non-piercing if for any pair of regions A and B, \(A{\setminus } B\) and \(B{\setminus } A\) are connected.
Union complexity of a set of objects is the description complexity of the boundary of the union of the objects.
We call an object \(A\subset {\mathbb {R}}^2\) fat, if the ratio of the radii of the smallest disk enclosing A and the largest disk enclosed by A is bounded by some fixed constant.
Actually, Lemma 1 proves for the discrete intersection which is a super graph of the bipartite version.
References
Agarwal PK, Pach J, Sharir M (2007) State of the union (of geometric objects): a review
Aschner R, Katz MJ, Morgenstern G, Yuditsky Y (2013) Approximation schemes for covering and packing. In: Proceedings of the seventh international workshop on algorithms and computation, WALCOM, pp 89–100
Ashok P, Kolay S, Misra N, Saurabh S (2015) Unique covering problems with geometric sets. In: Proceedings of the twenty-first international computing and combinatorics conference, COCOON, pp 548–558
Bandyapadhyay S, Basu Roy A (2017) Effectiveness of local search for art gallery problems. In: Procedings of the fifteenth international symposium on algorithms and data structures, WADS, pp 49–60
Bansal N, Pruhs K (2016) Weighted geometric set multi-cover via quasi-uniform sampling. J Comput Geom 7(1):221–236
Cesati M, Trevisan L (1997) On the efficiency of polynomial time approximation schemes. Inf Process Lett 64(4):165–171
Chan TM, Har-Peled S (2012) Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput Geom 48(2):373–392
Chekuri C, Clarkson KL, Har-Peled S (2012) On the set multicover problem in geometric settings. ACM Trans Algorithms (TALG) 9(1):9
Cohen-Addad V, Mathieu C (2015) Effectiveness of local search for geometric optimization. In: Proceedings of the thirty-first international symposium on computational geometry, SoCG, pp 329–343
Cohen-Addad V, Klein PN, Mathieu C (2016) Local search yields approximation schemes for $k$-means and $k$-median in euclidean and minor-free metrics. In: Proceedings of the IEEE fifty-seventh annual symposium on foundations of computer science, FOCS, pp 353–364
Dahllöf V, Jonsson P, Beigel R (2004) Algorithms for four variants of the exact satisfiability problem. Theor Comput Sci 320(2–3):373–394
Demaine ED, Feige U, Hajiaghayi M, Salavatipour MR (2008) Combination can be hard: approximability of the unique coverage problem. SIAM J Comput 38(4):1464–1483
Ene A, Har-Peled S, Raichel B (2012) Geometric packing under non-uniform constraints. In: Proceedings of the twenty-eighth annual symposium on computational geometry, SoCG, pp 11–20
Erlebach T, Van Leeuwen EJ (2008) Approximating geometric coverage problems. In: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA, pp 1267–1276
Fowler RJ, Paterson MS, Tanimoto SL (1981) Optimal packing and covering in the plane are NP-complete. Inf Process Lett 12(3):133–137
Frederickson GN (1987) Fast algorithms for shortest paths in planar graphs, with applications. SIAM J Comput 16(6):1004–1022
Friggstad Z, Rezapour M, Salavatipour MR (2016) Local search yields a PTAS for k-means in doubling metrics. In: Proceedings of the IEEE fifty-seventh annual symposium on foundations of computer science, FOCS, pp 365–374
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York
Govindarajan S, Raman R, Ray S, Basu Roy A (2016) Packing and covering with non-piercing regions. In: Procedings of the twenty-fourth annual european symposium on algorithms, ESA, pp 47:1–47:17
Har-Peled S (2014) Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: Proceedings of the thirtieth annual symposium on computational geometry, soCG, pp 120:120–120:129
Ito T, Nakano S-I, Okamoto Y, Otachi Y, Uehara R, Uno T, Uno Y (2012) A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares. In: Proceedings of the thirteenth scandinavian conference on algorithm theory, SWAT, pp 24–35. Springer
Ito T, Nakano S, Okamoto Y, Otachi Y, Uehara R, Uno T, Uno Y (2014) A 4.31-approximation for the geometric unique coverage problem on unit disks. Theor Comput Sci 544:14–31
Krohn E, Gibson M, Kanade G, Varadarajan K (2014) Guarding terrains via local search. J Comput Geom 5(1):168–178
Matoušek J (2002) Lectures on discrete geometry. Springer, Secaucus
Misra N, Moser H, Raman V, Saurabh S, Sikdar S (2013) The parameterized complexity of unique coverage and its variants. Algorithmica 65(3):517–544
Mustafa NH, Ray S (2010) Improved results on geometric hitting set problems. Discrete Comput Geom 44(4):883–895
Pach J, Walczak B (2016) Decomposition of multiple packings with subquadratic union complexity. Combin Probab Comput 25(1):145–153
Pyrga E, Ray S (2008) New existence proofs for $\epsilon $-nets. In: Proceedings of the twenty-fourth annual symposium on computational geometry, SoCG, pp 199–207
Schaefer TJ (1978) The complexity of satisfiability problems. In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC, pp 216–226
Whitesides S, Zhao R (1990) K-admissible collections of Jordan curves and offsets of circular arc figures. Technical report (McGill University. School of Computer Science). McGill University, School of Computer Science
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ashok, P., Basu Roy, A. & Govindarajan, S. Local search strikes again: PTAS for variants of geometric covering and packing. J Comb Optim 39, 618–635 (2020). https://doi.org/10.1007/s10878-019-00432-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00432-y