Data structures for halfplane proximity queries and incremental Voronoi diagrams

DOI10.1007/s00453-017-0389-yzbMath1410.68361arXivcs/0512091OpenAlexW2766893803MaRDI 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 structurestreesVoronoi diagramsflarbs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (9)

Compressing spatio-temporal trajectories ⋮ Incremental Voronoi diagrams ⋮ Dynamic minimum bichromatic separating circle ⋮ Approximating the discrete center line segment in linear time ⋮ Efficient \(k\)-center algorithms for planar points in convex position ⋮ Compressing Spatio-temporal Trajectories ⋮ Conic nearest neighbor queries and approximate Voronoi diagrams ⋮ A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters ⋮ On the minimum total length of interval systems expressing all intervals, and range-restricted queries

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

This page was built for publication: Data structures for halfplane proximity queries and incremental Voronoi diagrams