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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Point location problems for $n$ points in $d$-dimensional Euclidean space(and $\ell_p$ spaces more generally) have typically had two kinds ofrunning-time solutions:  * (Nearly-Linear) less than $d^{poly(d)} \cdot n \log^{O(d)} n$ time, or  * (Barely-Subquadratic) $f(d) \cdot n^{2-1/\Theta(d)}$ time, for various $f$.  For small $d$ and large $n$, "nearly-linear" running times are generallyfeasible, while "barely-subquadratic" times are generally infeasible. Forexample, in the Euclidean metric, finding a Closest Pair among $n$ points in${\mathbb R}^d$ is nearly-linear, solvable in $2^{O(d)} \cdot n \log^{O(1)} n$time, while known algorithms for Furthest Pair (the diameter of the point set)are only barely-subquadratic, requiring $\Omega(n^{2-1/\Theta(d)})$ time. Whydo these proximity problems have such different time complexities? Is there abarrier to obtaining nearly-linear algorithms for problems which are currentlyonly barely-subquadratic?  We give a novel exact and deterministic self-reduction for the OrthogonalVectors problem on $n$ vectors in $\{0,1\}^d$ to $n$ vectors in ${\mathbbZ}^{\omega(\log d)}$ that runs in $2^{o(d)}$ time. As a consequence,barely-subquadratic problems such as Euclidean diameter, Euclidean bichromaticclosest pair, ray shooting, and incidence detection do not have$O(n^{2-\epsilon})$ time algorithms (in Turing models of computation) fordimensionality $d = \omega(\log \log n)^2$, unless the popular OrthogonalVectors Conjecture and the Strong Exponential Time Hypothesis are false. Thatis, while poly-log-log-dimensional Closest Pair is in $n^{1+o(1)}$ time, theanalogous case of Furthest Pair can encode larger-dimensional problemsconjectured to require $n^{2-o(1)}$ time. We also show that the All-NearestNeighbors problem in $\omega(\log n)$ dimensions requires $n^{2-o(1)}$ time tosolve, assuming either of the above conjectures.

On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry