Data structures for halfplane proximity queries and incremental Voronoi diagrams

DOI10.1007/s00453-017-0389-yzbMath1410.68361arXivcs/0512091MaRDI QIDQ1755746

Erik D. Demaine, Boris Aronov, John Iacono, Prosenjit Bose, Joachim Gudmundsson, Stefan Langerman, Michiel H. M. Smid

Publication date: 11 January 2019

Published in: Algorithmica, LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0512091

zbMATH Keywords

data structures; trees; Voronoi diagrams; flarbs

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Compressing Spatio-temporal Trajectories, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Compressing spatio-temporal trajectories, On the minimum total length of interval systems expressing all intervals, and range-restricted queries, Incremental Voronoi diagrams, Conic nearest neighbor queries and approximate Voronoi diagrams, Dynamic minimum bichromatic separating circle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Making data structures persistent
• The farthest point Delaunay triangulation minimizes angles
• A data structure for dynamic trees
• Farthest-point queries with geometric and combinatorial constraints
• Incremental Voronoi diagrams
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• Optimal Point Location in a Monotone Subdivision
• Self-adjusting binary search trees
• Computational Geometry in C