RECORD
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon
Computational Geometry · Submitted 15 Mar 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set $S$ of point sites in a static simple polygon $P$. Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set $S$ of point sites in a static simple polygon $P$. | contribution 1.00 | 0.94 | 0.44 | asserted 1.00 |
| s1 | Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. | contribution 0.93 | 0.88 | 0.09 | asserted 1.00 |
| s2 | All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. | background 0.81 | 0.23 | 0.04 | asserted 1.00 |
| s3 | Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$. | result 0.85 | 0.95 | 0.57 | asserted 1.00 |
| s4 | The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. | method 0.83 | 0.86 | 0.14 | asserted 1.00 |
| s5 | We show that such an implicit representation exists, and that we can compute it efficiently. | contribution 0.66 | 0.95 | 0.13 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set $S$ of point sites in a static simple polygon $P$. Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
Human review
How the literature uses it
1 arXiv paper cite this in 4 sentences
Papers citing it · 3 sentences without a confident label
Uses its method or tool 1 paper
-
Therefore, we can use the exactly the same machinery as in Agarwal, Arge, and Staals [ref] , we compute $S'$ in $O(n(logn + log^2 m)$, time and then construct $$ in additional $O(nlog^2 m)$ time.
Nearest Neighbor Searching in a Dynamic Simple Polygon · $$ as an Hamiltonian abstract Voronoi diagram · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.