Home Bookmarks Papers Blog

On Locality-Sensitive Orderings and Their Applications $\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$

Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones.
For any constant $d$ and parameter $\eps > 0$, we show the existence of (roughly) $1/\eps^d$ orderings on the unit cube $[0,1)^d$, such that any two points $\pt,\ptq\in [0,1)^d$ that are close together under the Euclidean metric are ``close together'' in one of these linear orderings in the following sense: the only points that could lie between $\pt$ and $\ptq$ in the ordering are points with Euclidean distance at most $\eps\distY{\pt}{\ptq}$ from $\pt$ or $\ptq$. 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.

Last modified: Fri 2018-09-28 17:19:30 UTC 2018 by Sariel Har-Peled