We present subquadratic algorithms in the algebraic decision-tree model for several textsc{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 $Deltain C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Delta$. 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^2/log^2n)log^{O(1)}log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+varepsilon})$, for any $varepsilon>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 emph{order type} of the lines, a handicap that turns out to be beneficial for speeding up our algorithm.
Download