Name
Abstract | ||
|---|---|---|
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set of point sites $S$ a static simple polygon $P$. Our data structure allows us to insert a new site $S$, delete a site from $S$, and ask for the site $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 $P$. Our data structure supports queries $O(sqrt{n}log nlog^2 m)$ time, where $n$ is the number of sites currently $S$, and $m$ is the number of vertices of $P$, and updates $O(sqrt{n}log^3 m)$ time. The space usage is $O(nlog m + m)$. If only insertions are allowed, we can support queries worst-case $O(log^2 nlog^2 m)$ time, while allowing for $O(log nlog^3 m)$ amortized time insertions. We can achieve the same running times case there are both insertions and deletions, but the order of these operations is known advance. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computational Geometry | k-nearest neighbors algorithm,Binary logarithm,Data structure,Discrete mathematics,Combinatorics,Shortest path problem,Vertex (geometry),Amortized analysis,Simple polygon,Mathematics,Geodesic |
DocType | Volume | Citations |
Journal | abs/1707.02961 | 0 |
PageRank | References | Authors |
0.34 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lars Arge | 1 | 2066 | 255.14 |
| Frank Staals | 2 | 29 | 11.40 |