Dynamic data structures for \(k\)-nearest neighbor queries

DOI10.1016/j.comgeo.2022.101976arXiv2109.11854OpenAlexW3215321597MaRDI QIDQ6101840

Frank Staals, Sarita de Berg

Publication date: 20 June 2023

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.11854

zbMATH Keywords

geodesic distancedata structuresimple polygonnearest neighbor searching

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)

Related Items (1)

Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• The design of dynamic data structures
• Reporting points in halfspaces
• Optimal shortest path queries in a simple polygon
• Dynamic half-space range reporting and its applications
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• An optimal algorithm for selection in a min-heap
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• On Range Searching with Semialgebraic Sets. II
• Nearest neighbor pattern classification
• Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

This page was built for publication: Dynamic data structures for \(k\)-nearest neighbor queries