On Locality-Sensitive Orderings and Their Applications
Timothy M. Chan, Sariel Har-Peled, Mitchell Jones · SIAM Journal on Computing · 2020
For any constant $d$ and parameter $\varepsilon \in (0,1/2]$, we show the existence of (roughly) $1/\varepsilon^d$ orderings on the unit cube $[0,1)^d$ such that for any two points $p, q\in [0,1)^d$ close together under the Euclidean metric, there is a linear ordering in which all points between $p$ and $q$ in the ordering are “close” to $p$ or $q$. More precisely, the only points that could lie between $p$ and $q$ in the ordering are points with Euclidean distance at most $\varepsilon\left\| {p} - {q} \right\|$ from either $p$ or $q$. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.