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

The 3SUM problem asks if an input $n$-set of real numbers contains a triplewhose sum is zero. We consider the 3POL problem, a natural generalization of3SUM where we replace the sum function by a constant-degree polynomial in threevariables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave a$O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomialequations when the solutions are taken from the cartesian product of three$n$-sets of real numbers. We give algorithms for the corresponding problem ofcounting such solutions. Gr\o nlund and Pettie recently designed subquadraticalgorithms for 3SUM. We generalize their results to 3POL. Finally, we shedlight on the General Position Testing (GPT) problem: "Given $n$ points in theplane, do three of them lie on a line?", a key problem in computationalgeometry.  We prove that there exist bounded-degree algebraic decision trees of depth$O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solvedin $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in thereal-RAM model. Among the possible applications of those results, we show howto solve GPT in subquadratic time when the input points lie on $o({(\logn)}^\frac{1}{6}/{(\log \log n)}^\frac{1}{2})$ constant-degree polynomialcurves. This constitutes a first step towards closing the major open questionof whether GPT can be solved in subquadratic time.  To obtain these results, we generalize important tools --- such as batchrange searching and dominance reporting --- to a polynomial setting. We expectthese new tools to be useful in other applications.

Subquadratic Algorithms for Algebraic Generalizations of 3SUM