Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions

DOI10.1137/20M1388371MaRDI QIDQ5864671zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometryrandomized algorithmsrange searchingshallow cuttingsgeneral distance functionsrandomized data structures\(k\) nearest neighbors searching

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 410386 (Why is no real title available?)
• scientific article; zbMATH DE number 431985 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 7559224 (Why is no real title available?)
• A deterministic view of random sampling and its use in geometry
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• A note on Euclidean near neighbor searching in the plane
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• An improved bound for \(k\)-sets in three dimensions
• Applications of random sampling in computational geometry. II
• Computational geometry. Algorithms and applications.
• Computing Many Faces in Arrangements of Lines and Segments
• Concrete and abstract Voronoi diagrams
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Dynamic connectivity: connecting to networks and geometry
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Geometric retrieval problems
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• New applications of random sampling in computational geometry
• New upper bounds for neighbor searching
• On bounded leg shortest paths problems
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• On lazy randomized incremental construction
• On range searching with semialgebraic sets
• On range searching with semialgebraic sets. II.
• On the complexity of higher order abstract Voronoi diagrams
• Optimal Point Location in a Monotone Subdivision
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Optimal halfspace range reporting in three dimensions
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase(\le k)-Levels in Three Dimensions
• Relative (p, )-approximations in geometry
• Reporting points in halfspaces
• Shortest paths in intersection graphs of unit disks
• Spanners for geometric intersection graphs with applications
• Triangulating a simple polygon in linear time
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• Voronoi diagrams and Delaunay triangulations

Cited in

(8)

• Dynamic connectivity in disk graphs
• Fully-adaptive dynamic connectivity of square intersection graphs
• An improved algorithm for shortest paths in weighted unit-disk graphs
• Segment proximity graphs and nearest neighbor queries amid disjoint segments
• Dynamic data structures for \(k\)-nearest neighbor queries
• Maximum matchings in geometric intersection graphs
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• An algorithmic framework for the single source shortest path problem with applications to disk graphs

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)