Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
DOI10.1137/20M1388371OpenAlexW2981835202MaRDI QIDQ5864671
Publication date: 8 June 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1388371
computational geometryrandomized algorithmsrange searchingshallow cuttingsgeneral distance functionsrandomized data structures\(k\) nearest neighbors searching
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20) Combinatorial complexity of geometric structures (52C45)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
- Relative \((p,\varepsilon )\)-approximations in geometry
- On bounded leg shortest paths problems
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- A deterministic view of random sampling and its use in geometry
- Triangulating a simple polygon in linear time
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Concrete and abstract Voronoi diagrams
- Reporting points in halfspaces
- A note on Euclidean near neighbor searching in the plane
- On range searching with semialgebraic sets
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Shortest paths in intersection graphs of unit disks
- On the complexity of higher order abstract Voronoi diagrams
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- Voronoi Diagrams and Delaunay Triangulations
- Spanners for geometric intersection graphs with applications
- Dynamic Connectivity: Connecting to Networks and Geometry
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- Geometric retrieval problems
- New upper bounds for neighbor searching
- Optimal Point Location in a Monotone Subdivision
- An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Computing Many Faces in Arrangements of Lines and Segments
- Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- On Range Searching with Semialgebraic Sets. II
- On lazy randomized incremental construction
- An improved bound for \(k\)-sets in three dimensions
This page was built for publication: Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions