English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present subquadratic algorithms in the algebraic decision-tree model forseveral \textsc{3Sum}-hard geometric problems, all of which can be reduced tothe 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 theplane, we want to count, for each triangle $\Delta\in C$, the number ofintersection points between the segments of $A$ and those of $B$ that lie in$\Delta$. The problems considered in this paper have been studied byChan~(2020), who gave algorithms that solve them, in the standard real-RAMmodel, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in thealgebraic 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, whichexploits the multi-level polynomial partitioning machinery recently developedby 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} ofthe lines, a "handicap" that turns out to be beneficial for speeding up ouralgorithm.

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