Document Open Access Logo

Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set

Author Nabil H. Mustafa

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.87.pdf
  • Filesize: 491 kB
  • 12 pages

Document Identifiers

Author Details

Nabil H. Mustafa
  • Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, ESIEE Paris, France

Funding

This research was supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).

Acknowledgements

We thank the reviewers for insightful feedback that helped the content and presentation of this work.

Cite AsGet BibTex

Nabil H. Mustafa. Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 87:1-87:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.87

Abstract

Given a set system (X, R) with VC-dimension d, the celebrated result of Haussler and Welzl (1987) showed that there exists an epsilon-net for (X, R) of size O(d/epsilon log 1/epsilon). Furthermore, the algorithm is simple: just take a uniform random sample from X! However, for many geometric set systems this bound is sub-optimal and since then, there has been much work presenting improved bounds and algorithms tailored to specific geometric set systems. In this paper, we consider the following natural algorithm to compute an epsilon-net: start with an initial random sample N. Iteratively, as long as N is not an epsilon-net for R, pick any unhit set S in R (say, given by an Oracle), and add O(1) randomly chosen points from S to N. We prove that the above algorithm computes, in expectation, epsilon-nets of asymptotically optimal size for all known cases of geometric set systems. Furthermore, it makes O(1/epsilon) calls to the Oracle. In particular, this implies that computing optimal-sized epsilon-nets are as easy as computing an unhit set in the given set system.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • epsilon-nets
  • Geometric Set Systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal. Range Searching. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, 2017. Google Scholar
  2. P. K. Agarwal and J. Pan. Near-Linear Algorithms for Geometric Hitting Sets and Set Covers. In Symposium on Computational Geometry, page 271, 2014. Google Scholar
  3. N. Alon and J. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008. Google Scholar
  4. B. Aronov, E. Ezra, and M. Sharir. Small-size ε-nets for axis-parallel rectangles and boxes. SIAM Journal on Computing, 39(7):3248-3282, 2010. Google Scholar
  5. N. Bus, S. Garg, N. H. Mustafa, and S. Ray. Tighter estimates for ε-nets for disks. Computational Geometry: Theory and Applications, 53:27-35, 2016. Google Scholar
  6. T. M. Chan, E. Grant, J. Könemann, and M. Sharpe. Weighted Capacitated, Priority, and Geometric Set Cover via Improved Quasi-uniform Sampling. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1576-1585, 2012. Google Scholar
  7. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000. Google Scholar
  8. K. L. Clarkson. A Randomized Algorithm for Closest-Point Queries. SIAM J. Comput., 17(4):830-847, 1988. Google Scholar
  9. K. L. Clarkson and P. W. Shor. Application of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. Google Scholar
  10. K. L. Clarkson and K. R. Varadarajan. Improved approximation algorithms for geometric set cover. In Proceedings of the 21st Annual ACM Symposium on Computational Geometry (SoCG), pages 135-141, 2005. Google Scholar
  11. D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. Google Scholar
  12. J. Komlós, J. Pach, and G. Woeginger. Almost tight bounds for ε-nets. Discrete & Computational Geometry, 7:163-173, 1992. Google Scholar
  13. M. Matheny and J. M. Phillips. Practical Low-Dimensional Halfspace Range Space Sampling. In 26th Annual European Symposium on Algorithms (ESA), pages 62:1-62:14, 2018. Google Scholar
  14. J. Matoušek. Lectures on Discrete Geometry. Springer, 2002. Google Scholar
  15. J. Matoušek. Reporting Points in Halfspaces. Computational Geometry: Theory and Applications, 2(3):169-186, 1992. Google Scholar
  16. J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics. Springer, 1999. Google Scholar
  17. N. H. Mustafa. A Simple Proof of the Shallow Packing Lemma. Discrete & Computational Geometry, 55(3):739-743, 2016. Google Scholar
  18. N. H. Mustafa, K. Dutta, and A. Ghosh. A Simple Proof of Optimal Epsilon-nets. Combinatorica, 38(5):1269-1277, 2018. Google Scholar
  19. N. H. Mustafa and K. Varadarajan. Epsilon-approximations and Epsilon-nets. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, 2017. Google Scholar
  20. J. Pach and P. K. Agarwal. Combinatorial geometry. John Wiley &Sons, 1995. Google Scholar
  21. J. Phillips. Coresets and Sketches. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, 2017. Google Scholar
  22. E. Pyrga and S. Ray. New existence proofs for ε-nets. In Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG), pages 199-207, 2008. Google Scholar
  23. K. R. Varadarajan. Weighted Geometric Set Cover via Quasi-uniform Sampling. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 641-648, 2010. Google Scholar
  24. H. Yu, P. K. Agarwal, R. Poreddy, and K. R. Varadarajan. Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets. Algorithmica, 52(3):378-402, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact