Document Open Access Logo

Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications

Authors Mónika Csikós, Nabil H. Mustafa

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.28.pdf
  • Filesize: 1.9 MB
  • 17 pages

Document Identifiers

Author Details

Mónika Csikós
  • Université Gustave Eiffel, LIGM, Equipe A3SI, ESIEE Paris, Cité Descartes 2 boulevard Blaise Pascal, 93162 Noisy-le-Grand Cedex, France
Nabil H. Mustafa
  • Université Gustave Eiffel, LIGM, Equipe A3SI, ESIEE Paris, Cité Descartes 2 boulevard Blaise Pascal, 93162 Noisy-le-Grand Cedex, France

Funding

The work of the authors has been supported by the grants ANR ADDS (ANR-19-CE48-0005) and ANR SAGA (JCJC-14-CE25-0016-01).

Cite AsGet BibTex

Mónika Csikós and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.28

Abstract

Given a set system (X, S), constructing a matching of X with low crossing number is a key tool in combinatorics and algorithms. In this paper we present a new sampling-based algorithm which is applicable to finite set systems. Let n = |X|, m = | S| and assume that X has a perfect matching M such that any set in 𝒮 crosses at most κ = Θ(n^γ) edges of M. In the case γ = 1- 1/d, our algorithm computes a perfect matching of X with expected crossing number at most 10 κ, in expected time Õ (n^{2+(2/d)} + mn^(2/d)). As an immediate consequence, we get improved bounds for constructing low-crossing matchings for a slew of both abstract and geometric problems, including many basic geometric set systems (e.g., balls in ℝ^d). This further implies improved algorithms for many well-studied problems such as construction of ε-approximations. Our work is related to two earlier themes: the work of Varadarajan (STOC '10) / Chan et al. (SODA '12) that avoids spatial partitionings for constructing ε-nets, and of Chan (DCG '12) that gives an optimal algorithm for matchings with respect to hyperplanes in ℝ^d. Another major advantage of our method is its simplicity. An implementation of a variant of our algorithm in C++ is available on Github; it is approximately 200 lines of basic code without any non-trivial data-structure. Since the start of the study of matchings with low-crossing numbers with respect to half-spaces in the 1980s, this is the first implementation made possible for dimensions larger than 2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Matchings
  • crossing numbers
  • approximations

Metrics

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

Supplementary Materials

References

  1. P. K. Agarwal. Simplex range searching. In Journey Through Discrete Mathematics, pages 1-30. Springer, 2017. Google Scholar
  2. P. K. Agarwal and J. Matoušek. On range searching with semialgebraic sets. Discrete & Computational Geometry, 11(4):393-418, 1994. Google Scholar
  3. P. K. Agarwal, J. Matoušek, and M. Sharir. On range searching with semialgebraic sets. II. SIAM Journal on Computing, 42(6):2039-2062, 2013. Google Scholar
  4. P. K. Agarwal and J. Pan. Near-linear algorithms for geometric hitting sets and set covers. In Proceedings of Symposium on Computational Geometry, SOCG’14, page 271–279, 2014. Google Scholar
  5. N. Alon, O. Ben-Eliezer, Y. Dagan, S. Moran, M. Naor, and E. Yogev. Adversarial laws of large numbers and optimal regret in online classification, 2021. URL: http://arxiv.org/abs/2101.09054.
  6. N. Alon, D. Haussler, and E. Welzl. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. In SoCG '87, 1987. Google Scholar
  7. N. Alon, S. Moran, and A. Yehudayoff. Sign rank versus VC dimension. In COLT, 2016. Google Scholar
  8. T. M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661–690, 2012. Google Scholar
  9. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1576-1585, 2012. Google Scholar
  10. B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom., page 467–489, 1989. Google Scholar
  11. C. Chekuri and K. Quanrud. Randomized MWU for positive LPs. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, page 358–377, 2018. Google Scholar
  12. C. Chekuri, J. Vondrák, and R. Zenklusen. Dependent randomized rounding for matroid polytopes and applications. arXiv preprint, 2009. URL: http://arxiv.org/abs/0909.4348.
  13. E. Ezra, S. Har-Peled, H. Kaplan, and M. Sharir. Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location. Discret. Comput. Geom., 64(1):109-173, 2020. Google Scholar
  14. S. P. Fekete, M. E. Lübbecke, and H. Meijer. Minimizing the stabbing number of matchings, trees, and triangulations. In Proceedings of Symposium on Discrete Algorithms (SODA), 2004. Google Scholar
  15. D. A. Freedman. On Tail Probabilities for Martingales. The Annals of Probability, 3(1):100-118, 1975. URL: https://doi.org/10.1214/aop/1176996452.
  16. P. Giannopoulos, M. Konzack, and W Mulzer. Low-crossing spanning trees: an alternative proof and experiments. In Proceedings of EuroCG, 2014. Google Scholar
  17. M. D. Grigoriadis and L. G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995. Google Scholar
  18. S. Har-Peled. Constructing planar cuttings in theory and practice. SIAM J. Comput., 29:2016-2039, 2000. Google Scholar
  19. S. Har-Peled. Approximating spanning trees with low crossing number. arXiv, abs/0907.1131, 2009. URL: http://arxiv.org/abs/0907.1131.
  20. D. Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995. Google Scholar
  21. M. Matheny and J. M. Phillips. Practical low-dimensional halfspace range space sampling. In Annual European Symposium on Algorithms (ESA), volume 112, pages 62:1-62:14, 2018. Google Scholar
  22. J. Matoušek. Efficient partition trees. Discrete & Computational Geometry, 8(3):315-334, 1992. Google Scholar
  23. J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Springer Berlin Heidelberg, 1999. Google Scholar
  24. J. Matoušek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013. Google Scholar
  25. J. Matoušek, E. Welzl, and L. Wernisch. Discrepancy and approximations for bounded VC-dimension. Combinatorica, 13(4):455-466, 1993. Google Scholar
  26. N. H. Mustafa. Computing optimal epsilon-nets is as easy as finding an unhit set. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 87:1-87:12, 2019. Google Scholar
  27. N. H. Mustafa, K. Dutta, and A. Ghosh. A simple proof of optimal epsilon-nets. Combinatorica, 38(5):1269-1277, 2018. Google Scholar
  28. 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
  29. K. R. Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 641-648, 2010. Google Scholar
  30. H. E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167-178, 1968. Google Scholar
  31. E. Welzl. Partition trees for triangle counting and other range searching problems. In Proceedings of Annual Symposium on Computational Geometry (SoCG), page 23–33, 1988. Google Scholar
  32. E. Welzl. On spanning trees with low crossing numbers. In Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, page 233–249, 1992. 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