$ \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 $\eps \in (0,1)$, we present a new construction of $\eps$-locality-sensitive orderings (<LSOs) in $\Re^d$ of size $M = O(\Eps^{ d-1} \log \Eps)$, where $\Eps = 1/\eps$. This improves over previous work by a factor of $\Eps$, and is optimal up to a factor of $\log \Eps$. Such a set of LSOs has the property that for any two points, $\p, \q \in [0,1]^d$, there exist an order in the set such that all the points between $\p$ and $\q$ in the order are $\eps$-close to either $\p$ or $\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 \Eps$ factor) the lower bound, Thus offering a near-optimal simple dynamic data-structure for maintaining spanners under insertions and deletions.
Categories: cs.CG