TY - GEN

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

AU - Aronov, Boris

AU - de Berg, Mark

AU - Cardinal, Jean

AU - Ezra, Esther

AU - Iacono, John

AU - Sharir, Micha

N1 - Funding Information:
Micha Sharir: 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.
Funding Information:
Funding Boris Aronov: Partially supported by NSF Grants CCF-15-40656 and CCF-20-08551, and by Grant 2014/170 from the US-Israel Binational Science Foundation. Mark de Berg: Partially supported by the Dutch Research Council (NWO) through Gravitation Grant NETWORKS (project no. 024.002.003). Jean Cardinal: Partially supported by the F.R.S.-FNRS (Fonds National de la Recherche Scientifique) under CDR Grant J.0146.18. Esther Ezra: Partially supported by NSF CAREER under Grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation. John Iacono: Partially supported by Fonds National de la Recherche Scientifique (FNRS) under Grant no. MISU F.6001.1.
Publisher Copyright:
© Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - 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((n2/log2 n) logO(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n60/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.

AB - 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((n2/log2 n) logO(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n60/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.

KW - Algebraic decision-tree model

KW - Computational geometry

KW - Hierarchical partitions

KW - Order types

KW - Point location

KW - Polynomial partitioning

KW - Primal-dual range searching

UR - http://www.scopus.com/inward/record.url?scp=85122426490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85122426490&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2021.3

DO - 10.4230/LIPIcs.ISAAC.2021.3

M3 - Conference contribution

AN - SCOPUS:85122426490

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 32nd International Symposium on Algorithms and Computation, ISAAC 2021

A2 - Ahn, Hee-Kap

A2 - Sadakane, Kunihiko

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd International Symposium on Algorithms and Computation, ISAAC 2021

Y2 - 6 December 2021 through 8 December 2021

ER -