Near-Optimal Euclidean Locality-Sensitive Orderings
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911043030089728 |
|---|---|
| author | Gao, Zhimeng Har-Peled, Sariel |
| author_facet | Gao, Zhimeng Har-Peled, Sariel |
| contents | $ \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_12792 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Euclidean Locality-Sensitive Orderings Gao, Zhimeng Har-Peled, Sariel Computational Geometry $ \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. |
| title | Near-Optimal Euclidean Locality-Sensitive Orderings |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2310.12792 |