research-article

Small-size ε-nets for axis-parallel rectangles and boxes

Authors:

Micha ShairAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 639 - 648

https://doi.org/10.1145/1536414.1536501

Published: 31 May 2009 Publication History

Abstract

We show the existence of ε-nets of size O(1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in reals³ and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size

O(1/ε log log log 1/ε) for the dual range space of "fat" regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Bronnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding range spaces.

References

[1]

P. K. Agarwal, J. Matousek, and O. Schwarzkopf,Computing many faces in arrangements of lines and segments,phSIAM J. Comput., 27:491--505, 1998.

Digital Library

[2]

M. Bellare, S. Goldwasser, G. Lund, and A. Russell,Efficient probabilistically checkable proofs and applications to approximation. In Proc. 25th Annu. ACM Symp. Theory Comput., pp. 294--304, 1993.

Digital Library

[3]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth,Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension,phJ. ACM, 36(4):929--965, 1989.

Digital Library

[4]

J.D. Boissonnat, M. Sharir, B. Tagansky and M. Yvinec,Voronoi diagrams in higher dimensions under certain polyhedraldistance functions,phDiscrete Comput. Geom., 19:485--519, 1998.

[5]

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

Digital Library

[6]

H. Brönnimann and J. Lenchner,Fast almost-linear-sized nets for boxes in the plane.In Proc. 14th Annu. Fall Workshop Comput. Geom., pp. 36--38, 2004.

[7]

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

[8]

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

Digital Library

[9]

K. L. Clarkson, Algorithms for polytope covering and approximation.In Proc. 3rd Workshop on Algorithms and Data Structures, pages 246--252, 1993.

Digital Library

[10]

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

Digital Library

[11]

K. L. Clarkson and K. Varadarajan,Improved approximation algorithms for geometric set cover, Discrete Comput. Geom., 37:43--58, 2007.

Digital Library

[12]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, 2001.

Digital Library

[13]

M. de Berg,Improved bounds on the union complexity of fat objects, Discrete Comput. Geom., 40(1):127--140, 2008.

Digital Library

[14]

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications,3rd rev. ed., Springer-Verlag, Berlin, 2008.

Digital Library

[15]

A. Efrat,The complexity of the union of (α,β)-covered objects, SIAM J. Comput., 34:775--787, 2005.

Digital Library

[16]

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(1):523--539, 1989.

Digital Library

[17]

A. Efrat and M. Katz,On the union of κ-curved objects, Comput. Geom. Theory Appl. 14:241--254, 1999.

Digital Library

[18]

A. Efrat and M. Sharir,The complexity of the union of fat objects in the plane, Discrete Comput. Geom. 23:171--189, 2000.

[19]

T. Feder and D. H. Greene,Optimal algorithms for approximate clustering.In Proc. 20th Annu. ACM Symp. Theory Comput., pages 434--444, 1988.

Digital Library

[20]

U. Feige, A threshold of łnn for approximating set cover, J. ACM, 45(4):634--652, 1998.

Digital Library

[21]

R. Fowler, M. Paterson, and S. Tanimoto, Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12(3):133--137, 1981.

[22]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,W. H. Freeman, New York, NY, 1979.

Digital Library

[23]

S. Har-Peled, H. Kaplan, M. Sharir, and S. Smorodinsky, ε-nets for halfspaces revisited, manuscript, 2008.

[24]

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

Digital Library

[25]

H. Kaplan, N. Rubin, M. Sharir, and E. Verbin, Efficient colored orthogonal range counting, SIAM J. Comput., 38:982--1011, 2008.

Digital Library

[26]

R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, Eds., Complexity of Computer Computations, pages 85--103, Plenum Press, New York, 1972.

[27]

J. Komlós, J. Pach, and G. Woeginger, Almost tight bounds for epsilon nets, Discrete Comput. Geom., 7:163--173, 1992.

Digital Library

[28]

J. Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, 2002.

Digital Library

[29]

J. Matousek,Reporting points in halfspaces, Comput. Geom. Theory Appl. 2:169--186, 1992.

Digital Library

[30]

J. Matousek,Approximations and optimal geometric divide-and-conquer, J. Comput Sys. Sci., 50(2):203--208, 1995.

Digital Library

[31]

J. Matousek, R. Seidel, and E. Welzl,How to net a lot with little: Small ε-nets for disksand halfspaces.In phProc. 6th Annu. ACM Sympos. Comput. Geom., pages 16--22, 1990.Revised version at http://kam.mff.cuni.cz/matousek/enets3.ps.gz .

Digital Library

[32]

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

Digital Library

[33]

A. Naamad, D. T. Lee, and W. L. Hsu,On the maximal empty rectangle problem, Discrete Applied Math., 8:267--277, 1984.

[34]

J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley Interscience, New York, 1995.

Digital Library

[35]

J. Pach and G. Tardos,On the boundary complexity of the union of fat triangles, SIAM J. Comput., 31:1745--1760, 2002.

Digital Library

[36]

E. Pyrga and S. Ray,New existence proofs for ε-nets.In Proc. 24th Annu. ACM Sympos. Comput. Geom., pages 199--207, 2008.

Digital Library

[37]

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

Digital Library

[38]

K. Varadarajan, Epsilon nets and union complexity.In Proc. 25th Annu. ACM Sympos. Comput. Geom., 2009, to appear.

Digital Library

Cited By

Aarts SShmoys D(2023)Hitting Sets when the Shallow Cell Complexity is SmallApproximation and Online Algorithms10.1007/978-3-031-49815-2_12(160-174)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49815-2_12
Das AFleszar KKobourov SSpoerhase JVeeramoni SWolff A(2018)Approximating the Generalized Minimum Manhattan Network ProblemAlgorithmica10.1007/s00453-017-0298-080:4(1170-1190)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00453-017-0298-0
Bansal NPruhs K(2012)Weighted geometric set multi-cover via quasi-uniform samplingProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_14(145-156)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_14
Show More Cited By

Index Terms

Small-size ε-nets for axis-parallel rectangles and boxes
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Epsilon nets and union complexity
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

We consider the following combinatorial problem: given a set of n objects (for example, disks in the plane, triangles), and an integer L ≥ 1, what is the size of the smallest subset of these n objects that covers all points that are in at least L of the ...
Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes

We show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon}\right)$ for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane and “fat” triangular ranges ...
Near-linear approximation algorithms for geometric hitting sets
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

Given a set system (X,R), the hitting set problem is to find a smallest-cardinality subset H ⊆ X, with the property that each range R ∈ R has a non-empty intersection with H. We present near-linear time approximation algorithms for the hitting set ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 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: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
326
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aarts SShmoys D(2023)Hitting Sets when the Shallow Cell Complexity is SmallApproximation and Online Algorithms10.1007/978-3-031-49815-2_12(160-174)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49815-2_12
Das AFleszar KKobourov SSpoerhase JVeeramoni SWolff A(2018)Approximating the Generalized Minimum Manhattan Network ProblemAlgorithmica10.1007/s00453-017-0298-080:4(1170-1190)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00453-017-0298-0
Bansal NPruhs K(2012)Weighted geometric set multi-cover via quasi-uniform samplingProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_14(145-156)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_14
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
Varadarajan KMitzenmacher MSchulman L(2010)Weighted geometric set cover via quasi-uniform samplingProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806777(641-648)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806689.1806777
Ezra E(2010)A note about weak ε-nets for axis-parallel boxes in d-spaceInformation Processing Letters10.1016/j.ipl.2010.06.005110:18-19(835-840)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.ipl.2010.06.005
Berman PKarpinski MLingas A(2010)Exact and Approximation Algorithms for Geometric and Capacitated Set Cover ProblemsComputing and Combinatorics10.1007/978-3-642-14031-0_26(226-234)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14031-0_26
Chekuri CClarkson KHar-Peled SHershberger JFogel E(2009)On the set multi-cover problem in geometric settingsProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542421(341-350)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542421
Agarwal PEzra EShair MHershberger JFogel E(2009)Near-linear approximation algorithms for geometric hitting setsProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542368(23-32)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542368
Varadarajan KHershberger JFogel E(2009)Epsilon nets and union complexityProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542366(11-16)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542366

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents