Article

Improved approximation algorithms for geometric set cover

Authors:

Kenneth L. Clarkson,

Kasturi VaradarajanAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 135 - 141

https://doi.org/10.1145/1064092.1064115

Published: 06 June 2005 Publication History

Abstract

Given a collection S of subsets of some set U, and M ⊂ U, the set cover problem is to find the smallest subcollection C ⊂ S such that M is a subset of the union of the sets in C. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually U = R^d. Combining previously known techniques [3, 4], we show that polynomial time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R ⊂ S and function f(), there is a decomposition of the complement U ∖ ∪_{Y ∈ R} Y into an expected f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudodisks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in R³, and for guarding an x-monotone polygonal chain.

References

[1]

B. Ben-Moshe, M. J. Katz, and J. S. B. Mitchell. A constant-factor approximation algorithm for optimal terrain guarding. In Proc. ACM-SIAM Symposium on Discrete Algorithms, to appear, 2005.

Digital Library

[2]

J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom., 19(4):473--484, 1998.

[3]

H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom., 14:263--279, 1995.

Digital Library

[4]

B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10, 1990.

[5]

V. Chvátal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4:233--235, 1979.

Digital Library

[6]

K. L. Clarkson. New applications of random sampling in computational geometry. Discrete Comput. Geom., 2:195--222, 1987.

Digital Library

[7]

K. L. Clarkson. Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes Comput. Sci., pages 246--252. Springer-Verlag, 1993.

Digital Library

[8]

K. L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM, 42(2):488--499, 1995.

Digital Library

[9]

K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comp. Geom.: Theory and Applications, pages 185--121, 1993.

Digital Library

[10]

K. L. Clarkson and P. Shor. Applications of random sampling in computational geometry, II. Discrete and Computational Geometry, 4:387--421, 1989.

Digital Library

[11]

G. Cǎlinescu, I. Mǎndoiu, P. Wan, and A. Zelikovsky. Selecting forwarding neighbors in wireless ad hoc networks. Mobile Networks and Applications, 9:101--111, 2004.

Digital Library

[12]

H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink. On arrangements of jordan arcs with three intersections per pair. Discrete Comput. Geom, 4:523--539, 1989.

Digital Library

[13]

A. Efrat. The complexity of the union of (α, β)-covered objects. In Proc. 15th Annual Symposium on Computational Geometry, pages 134--142, 1999.

Digital Library

[14]

A. Efrat, G. Rote, and M. Sharir. On the union of fat wedges and separating a collection of segments by a line. Comput. Geom. Theory Appls, 3:277--288, 1994.

Digital Library

[15]

G. Even, D. Rawitz, and S. Shahar. Hitting sets when the VC-dimension is small. Manuscript, http://www.eng.tau.ac.il/ guy/Papers/VC.pdf+.

[16]

U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45:634--652, 1998.

Digital Library

[17]

D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom., 2:127--151, 1987.

Digital Library

[18]

D. S. Hochbaum and W. Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32:130--136, 1985.

Digital Library

[19]

D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9:256--278, 1974.

Digital Library

[20]

K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of jordan regions and collision free translational motion amidst polygonal obstacles. Discrete Comput., 1:59--71, 1986.

Digital Library

[21]

V. S. A. Kumar and H. Ramesh. Covering rectilinear polygons with axis-parallel rectangles. SIAM J. Comput., 32(6):1509--1541, 2003.

Digital Library

[22]

N. Littlestone. Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. In Proc. 28th IEEE Symp. on Foundations of Computer Science, pages 68--77, 1987.

Digital Library

[23]

L. Lovász. On the ratio of optimal integral and fractional covers.Discrete Math., 13:383--390, 1975.

Digital Library

[24]

C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41:960--981, 1994.

Digital Library

[25]

J. Matoušek. Reporting points in halfspaces. Comput. Geom. Theory Appl., 2(3):169--186, 1992.

Digital Library

[26]

J. Matoušek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl. Fat triangles determine linearly many holes. SIAM J. Comput., 23:154--169, 1994.

Digital Library

[27]

J. Matoušek, R. Seidel, and E. Welzl. How to net a lot with little: small ε-nets for disks and halfspaces. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 16--22, 1990.

Digital Library

[28]

J. S. B. Mitchell and S. Suri. Separation and approximation of polyhedral objects. Comput. Geom. Theory Appl., 5:95--114, 1995.

Digital Library

[29]

K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.

[30]

M. Sharir. The complexity of the union of planar regions. http://imu.org.il/Meeting97/Abstracts/sharir.ps, 1997.

[31]

M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

Digital Library

[32]

E. Welzl. Partition trees for triangle counting and other range searching problems. In Proc. Fourth ACM Symp. on Comp. Geometry, pages 23--33, 1988.

Digital Library

Cited By

Acharyya AKeikha VMajumdar DPandit S(2024)Constrained hitting set problem with intervalsTheoretical Computer Science10.1016/j.tcs.2024.114402990:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114402
Bus NGarg SMustafa NRay S(2016)Tighter estimates for Ε-nets for disksComputational Geometry: Theory and Applications10.1016/j.comgeo.2015.12.00253:C(27-35)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.comgeo.2015.12.002
Althoff DScherer S(2015)Connected invariant sets for high-speed motion planning in partially-known environments2015 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2015.7139651(3279-3285)Online publication date: May-2015
https://doi.org/10.1109/ICRA.2015.7139651
Show More Cited By

Index Terms

Improved approximation algorithms for geometric set cover
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Improved Approximation Algorithms for Geometric Set Cover

Given a collection S of subsets of some set ${\Bbb U},$ and ${\Bbb M}\subset{\Bbb U},$ the set cover problem is to find the smallest subcollection $C\subset S$ that covers ${\Bbb M},$ that is, ${\Bbb M} \subseteq \bigcup (C),$ where $\bigcup(C)$ denotes ...
Partially Polynomial Kernels for Set Cover and Test Cover

An instance of the $(n-k)$-Set Cover or the $(n-k)$-Test Cover problems is of the form $(\mathcal{U},\mathcal{S},k)$, where $\mathcal{U}$ is a set with $n$ elements, $\mathcal{S}\subseteq 2^\mathcal{U}$ with $|\mathcal{S}|=m$, and $k$ is the parameter. The ...
Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search

In the unweighted set cover problem we are given a set of elements $E=\{e_1,e_2,\ldots,e_n\}$ and a collection ${\cal F}$ of subsets of $E$. The problem is to compute a subcollection $SOL\subseteq{\cal F}$ such that $\bigcup_{S_j\in SOL}S_j=E$ and its ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
873
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Acharyya AKeikha VMajumdar DPandit S(2024)Constrained hitting set problem with intervalsTheoretical Computer Science10.1016/j.tcs.2024.114402990:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114402
Bus NGarg SMustafa NRay S(2016)Tighter estimates for Ε-nets for disksComputational Geometry: Theory and Applications10.1016/j.comgeo.2015.12.00253:C(27-35)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.comgeo.2015.12.002
Althoff DScherer S(2015)Connected invariant sets for high-speed motion planning in partially-known environments2015 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2015.7139651(3279-3285)Online publication date: May-2015
https://doi.org/10.1109/ICRA.2015.7139651
Yun ZBai XXuan DJia WZhao W(2012)Pattern mutation in wireless sensor deploymentIEEE/ACM Transactions on Networking10.1109/TNET.2012.219951520:6(1964-1977)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1109/TNET.2012.2199515
Elbassioni KKrohn EMatijević DMestre JźEverdija D(2011)Improved Approximations for Guarding 1.5-Dimensional TerrainsAlgorithmica10.5555/3118782.311922360:2(451-463)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.5555/3118782.3119223
Gibson MKanade GVaradarajan K(2011)On isolating points using disksProceedings of the 19th European conference on Algorithms10.5555/2040572.2040580(61-69)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040580
Kasiviswanathan SZhao BVasudevan SUrgaonkar B(2011)Fast track articlePervasive and Mobile Computing10.1016/j.pmcj.2010.07.0037:1(114-127)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.pmcj.2010.07.003
Gibson MKanade GVaradarajan K(2011)On Isolating Points Using DisksAlgorithms – ESA 201110.1007/978-3-642-23719-5_6(61-69)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23719-5_6
Kasiviswanathan SZhao BVasudevan SUrgaonkar B(2010)Bandwidth provisioning in infrastructure-based wireless networks employing directional antennasProceedings of the 11th international conference on Distributed computing and networking10.5555/2018057.2018096(295-306)Online publication date: 3-Jan-2010
https://dl.acm.org/doi/10.5555/2018057.2018096
Berman PKarpinski MLingas A(2010)Exact and approximation algorithms for geometric and capacitated set cover problemsProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886843(226-234)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886843
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten