2026-07-23T04:53:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15436 2024-03-06T10:55:17Z ddc:004 open_access

Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model Aronov, Boris de Berg, Mark Cardinal, Jean Ezra, Esther Iacono, John Sharir, Micha Computational geometry Algebraic decision-tree model Polynomial partitioning Primal-dual range searching Order types Point location Hierarchical partitions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Mark de Berg and Jean Cardinal and Esther Ezra and John Iacono and Micha Sharir 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.3 urn:nbn:de:0030-drops-154363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode