Document Open Access Logo

Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

Authors Boris Aronov , Mark de Berg , Jean Cardinal , Esther Ezra , John Iacono , Micha Sharir

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2021.3.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Computational geometry
  • Algebraic decision-tree model
  • Polynomial partitioning
  • Primal-dual range searching
  • Order types
  • Point location
  • Hierarchical partitions

Metrics

Abstract

We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0.
Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020).
A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.

Cite As Get BibTex

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.3

Author Details

Boris Aronov
  • Tandon School of Engineering, New York University, Brooklyn, NY, USA
Mark de Berg
  • Eindhoven University of Technology, The Netherlands
Jean Cardinal
  • Université libre de Bruxelles (ULB), Brussels, Belgium
Esther Ezra
  • School of Computer Science, Bar Ilan University, Ramat Gan, Israel
John Iacono
  • Université libre de Bruxelles (ULB), Brussels, Belgium
  • Tandon School of Engineering, New York University, Brooklyn, NY, USA
Micha Sharir
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Aronov, Boris: Partially supported by NSF Grants CCF-15-40656 and CCF-20-08551, and by Grant 2014/170 from the US-Israel Binational Science Foundation.
  • de Berg, Mark: Partially supported by the Dutch Research Council (NWO) through Gravitation Grant NETWORKS (project no. 024.002.003).
  • Cardinal, Jean: Partially supported by the F.R.S.-FNRS (Fonds National de la Recherche Scientifique) under CDR Grant J.0146.18.
  • Ezra, Esther: Partially supported by NSF CAREER under Grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation.
  • Iacono, John: Partially supported by Fonds National de la Recherche Scientifique (FNRS) under Grant no. MISU F.6001.1.
  • Sharir, Micha: Partially supported by ISF Grant 260/18, by Grant 1367/2016 from the German-Israeli Science Foundation (GIF), and by Blavatnik Research Fund in Computer Science at Tel Aviv University.

Acknowledgements

We thank Zuzana Patáková for helpful discussions on multilevel polynomial partitioning.

References

  1. Pankaj K. Agarwal. Parititoning arrangements of lines II: Applications. Discret. Comput. Geom., 5:533-573, 1990. URL: https://doi.org/10.1007/BF02187809.
  2. Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. Efficient algorithm for generalized polynomial partitioning and its applications. SIAM J. Comput., 50(2):760-787, 2021. URL: https://doi.org/10.1137/19M1268550.
  3. Pankaj K. Agarwal, Marco Pellegrini, and Micha Sharir. Counting circular arc intersections. SIAM J. Comput., 22(4):778-793, 1993. URL: https://doi.org/10.1137/0222050.
  4. Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model. CoRR, abs/2109.07587, 2021. URL: http://arxiv.org/abs/2109.07587.
  5. Boris Aronov, Esther Ezra, and Micha Sharir. Testing polynomials for vanishing on cartesian products of planar point sets. In 36th International Symposium on Computational Geometry, SoCG 2020, volume 164 of LIPIcs, pages 8:1-8:14, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.8.
  6. Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic algorithms for algebraic 3Sum. Discret. Comput. Geom., 61(4):698-734, 2019. URL: https://doi.org/10.1007/s00454-018-0040-y.
  7. Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pages 80-86. ACM, 1983. URL: https://doi.org/10.1145/800061.808735.
  8. Jürgen Bokowski, Simon King, Susanne Mock, and Ileana Streinu. The topological representation of oriented matroids. Discret. Comput. Geom., 33(4):645-668, 2005. URL: https://doi.org/10.1007/s00454-005-1164-4.
  9. Jürgen Bokowski, Susanne Mock, and Ileana Streinu. On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3. Eur. J. Comb., 22(5):601-615, 2001. URL: https://doi.org/10.1006/eujc.2000.0482.
  10. Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM using few linear queries. In 24th Annual European Symposium on Algorithms, ESA 2016, volume 57 of LIPIcs, pages 25:1-25:17, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.25.
  11. Timothy M. Chan. More logarithmic-factor speedups for 3Sum, (median, +)-convolution, and some geometric 3Sum-hard problems. ACM Trans. Algorithms, 16(1):7:1-7:23, 2020. URL: https://doi.org/10.1145/3363541.
  12. Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica, 11(2):116-132, 1994. URL: https://doi.org/10.1007/BF01182771.
  13. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer, 2008. URL: https://www.worldcat.org/oclc/227584184.
  14. Mark de Berg and Otfried Schwarzkopf. Cuttings and applications. Int. J. Comput. Geom. Appl., 5(4):343-355, 1995. URL: https://doi.org/10.1142/S0218195995000210.
  15. Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15(2):317-340, 1986. URL: https://doi.org/10.1137/0215023.
  16. Esther Ezra, Sariel Har-Peled, Haim Kaplan, and Micha Sharir. Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location. Discret. Comput. Geom., 64(1):109-173, 2020. URL: https://doi.org/10.1007/s00454-019-00141-7.
  17. Esther Ezra and Micha Sharir. A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discret. Comput. Geom., 61(4):735-755, 2019. URL: https://doi.org/10.1007/s00454-018-0043-8.
  18. Jon Folkman and Jim Lawrence. Oriented matroids. J. Comb. Theory, Ser. B, 25(2):199-236, 1978. URL: https://doi.org/10.1016/0095-8956(78)90039-4.
  19. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  20. Omer Gold and Micha Sharir. Improved bounds for 3SUM, k-SUM, and linear degeneracy. In 25th Annual European Symposium on Algorithms, ESA 2017, volume 87 of LIPIcs, pages 42:1-42:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.42.
  21. Jacob E. Goodman and Richard Pollack. Multidimensional sorting. SIAM J. Comput., 12(3):484-507, 1983. URL: https://doi.org/10.1137/0212032.
  22. Jacob E. Goodman and Richard Pollack. Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory, Ser. A, 37(3):257-293, 1984. URL: https://doi.org/10.1016/0097-3165(84)90050-5.
  23. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM, 65(4):22:1-22:25, 2018. URL: https://doi.org/10.1145/3185378.
  24. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discret. Comput. Geom., 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
  25. Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. J. ACM, 66(3):16:1-16:18, 2019. URL: https://doi.org/10.1145/3285953.
  26. D. T. Lee and Franco P. Preparata. Location of a point in a planar subdivision and its applications. SIAM J. Comput., 6(3):594-606, 1977. URL: https://doi.org/10.1137/0206043.
  27. Jirí Matousek and Zuzana Patáková. Multilevel polynomial partitions and simplified range searching. Discret. Comput. Geom., 54(1):22-41, 2015. URL: https://doi.org/10.1007/s00454-015-9701-2.
  28. Stefan Meiser. Point location in arrangements of hyperplanes. Inf. Comput., 106(2):286-303, 1993. URL: https://doi.org/10.1006/inco.1993.1057.
  29. Neil Sarnak and Robert Endre Tarjan. Planar point location using persistent search trees. Commun. ACM, 29(7):669-679, 1986. URL: https://doi.org/10.1145/6138.6151.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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