  $ \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 (<em>LSO</em>s) 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.
