The Road to the Closest Point is Paved by Good Neighbors
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918177124909056 |
|---|---|
| author | Har-Peled, Sariel Raichel, Benjamin Robson, Eliot W. |
| author_facet | Har-Peled, Sariel Raichel, Benjamin Robson, Eliot W. |
| contents | $\renewcommand{\Re}{\mathbb{R}}$Given a set $P$ of $n$ points in $\Re^d$, and a parameter $\varepsilon \in (0,1)$, we present a new construction of a directed graph $G$, of size $O(n/\varepsilon^d)$, such that $(1+\varepsilon)$-ANN queries can be answered by performing a greedy walk on $G$, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is $O( \varepsilon^{-d} \log Ψ)$, where $Ψ$ is the spread of $P$. The new construction is surprisingly simple and should be practical. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23966 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Road to the Closest Point is Paved by Good Neighbors Har-Peled, Sariel Raichel, Benjamin Robson, Eliot W. Computational Geometry $\renewcommand{\Re}{\mathbb{R}}$Given a set $P$ of $n$ points in $\Re^d$, and a parameter $\varepsilon \in (0,1)$, we present a new construction of a directed graph $G$, of size $O(n/\varepsilon^d)$, such that $(1+\varepsilon)$-ANN queries can be answered by performing a greedy walk on $G$, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is $O( \varepsilon^{-d} \log Ψ)$, where $Ψ$ is the spread of $P$. The new construction is surprisingly simple and should be practical. |
| title | The Road to the Closest Point is Paved by Good Neighbors |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2509.23966 |