Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
Authors:
- Boris AronovBABoris Aronov
- Esther EzraEEEsther Ezra
- Micha SharirMSMicha Sharir
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (7) , 3248-3282
Abstract
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 and for point sets in $\boldsymbol{R}^3$ and axis-parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of $\varepsilon$-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\log\frac{1}{\varepsilon}\right)$ 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 Brönnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the hitting set or the set cover problems associated with the corresponding range spaces.
Keywords
This publication has 40 references indexed in Scilit:
- Improved Bounds on the Union Complexity of Fat ObjectsDiscrete & Computational Geometry, 2007
- Improved Approximation Algorithms for Geometric Set CoverDiscrete & Computational Geometry, 2006
- Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance FunctionsDiscrete & Computational Geometry, 1998
- Computing Many Faces in Arrangements of Lines and SegmentsSIAM Journal on Computing, 1998
- Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 1995
- A deterministic view of random sampling and its use in geometryCombinatorica, 1990
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequencesJournal of Combinatorial Theory, Series A, 1989
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989
- New applications of random sampling in computational geometryDiscrete & Computational Geometry, 1987