Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
DOI10.1137/20M1388371OpenAlexW2981835202MaRDI QIDQ5864671FDOQ5864671
Authors: Chih-Hung Liu 
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
Recommendations
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
- scientific article; zbMATH DE number 1559576
- Nearest neighbor queries in metric spaces
computational geometryrandomized algorithmsrange searchingshallow cuttingsgeneral distance functionsrandomized data structures\(k\) nearest neighbors searching
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)
Cites Work
- Concrete and abstract Voronoi diagrams
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Voronoi diagrams and Delaunay triangulations
- An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Title not available (Why is that?)
- Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Title not available (Why is that?)
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- Computational geometry. Algorithms and applications.
- A deterministic view of random sampling and its use in geometry
- On range searching with semialgebraic sets. II.
- Triangulating a simple polygon in linear time
- Title not available (Why is that?)
- Optimal Point Location in a Monotone Subdivision
- Title not available (Why is that?)
- Computing Many Faces in Arrangements of Lines and Segments
- On the complexity of higher order abstract Voronoi diagrams
- A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
- Optimal halfspace range reporting in three dimensions
- Shortest paths in intersection graphs of unit disks
- Spanners for geometric intersection graphs with applications
- Reporting points in halfspaces
- On range searching with semialgebraic sets
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- An improved bound for \(k\)-sets in three dimensions
- Relative \((p,\varepsilon )\)-approximations in geometry
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- On bounded leg shortest paths problems
- Geometric retrieval problems
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- On lazy randomized incremental construction
- Dynamic connectivity: connecting to networks and geometry
- A note on Euclidean near neighbor searching in the plane
- New upper bounds for neighbor searching
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Improved dynamic geodesic nearest neighbor searching in a simple polygon
- Title not available (Why is that?)
Cited In (4)
This page was built for publication: Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864671)
