Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

DOI10.1137/20M1388371OpenAlexW2981835202MaRDI QIDQ5864671

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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20) Combinatorial complexity of geometric structures (52C45)

Related Items (4)

Maximum matchings in geometric intersection graphs ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ An algorithmic framework for the single source shortest path problem with applications to disk graphs ⋮ Dynamic connectivity in disk graphs

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