2017/07/10 by Lars Arge, Frank Staals, Arge, Lars +1
Computer Science · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1707.02961
openalex publication_date 2017/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set of point sites S 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 ∈ 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 supports queries in O(√(n)log nlog2 m) time, where n is the number of sites currently in S, and m is the number of vertices of P, and updates in O(√(n)log3 m) time. The space usage is O(nlog m + m). If only insertions are allowed, we can support queries in worst-case O(log2 nlog2 m) time, while allowing for O(log nlog3 m) amortized time insertions. We can achieve the same running times in case there are both insertions and deletions, but the order of these operations is known in advance.