Near-Optimal Euclidean Locality-Sensitive Orderings

\newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Eps}{\Mh{\mathcal{E}}} \newcommand{\p}{\Mh{p}} \newcommand{\q}{\Mh{q}} \newcommand{\Mh}[1]{#1} \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} For a parameter $\text{eps}\in (0,1)$, we present a new construction of $\text{eps}$-locality-sensitive orderings (<LSOs) in ${\mathrm{\Re }}^d$ of size $M=O({\text{Eps}}^{d-1}\log \text{Eps})$, where $\text{Eps}=1\mathrm{/}\text{eps}$. This improves over previous work by a factor of $\text{Eps}$, and is optimal up to a factor of $\log \text{Eps}$. Such a set of LSOs has the property that for any two points, $\text{p},\text{q}\in [0,1{]}^d$, there exist an order in the set such that all the points between $\text{p}$ and $\text{q}$ in the order are $\text{eps}$-close to either $\text{p}$ or $\text{q}$. The existence of such LSOs is a fundamental property of low dimensional Euclidean space, conceptually similar to the existence of well-separated pairs decomposition, so the question of how to compute (near) optimal construction of LSOs is quite natural. As a consequence we get a flotilla of improved dynamic geometric algorithms, such as maintaining bichromatic closest pair, and spanners, among others. In particular, for geometric dynamic spanners the new result matches (up to the aforementioned $\log \text{Eps}$ factor) the lower bound, Thus offering a near-optimal simple dynamic data-structure for maintaining spanners under insertions and deletions.