A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

DOI10.1145/1706591.1706596zbMath1327.68314OpenAlexW2624483937MaRDI QIDQ3578196

Timothy M. Chan

Publication date: 14 July 2010

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1706591.1706596

zbMATH Keywords

computational geometryconvex hullsdynamic data structuresnearest neighbor search

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (22)

Minimum cuts in geometric intersection graphs ⋮ Spanners for Directed Transmission Graphs ⋮ Incremental Voronoi diagrams ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ Dynamic connectivity in disk graphs ⋮ Unnamed Item ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ Bounded-degree polyhedronization of point sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Kinetic Delaunay Triangulations ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Crushing Disks Efficiently ⋮ Two approaches to building time-windowed geometric data structures ⋮ Shortest paths in intersection graphs of unit disks ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

This page was built for publication: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries