A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters

DOI10.1007/s00453-016-0118-yzbMath1352.68265arXiv1312.3904MaRDI QIDQ727968

Evanthia Papadopoulou, Panagiotis Cheilaris, Stefan Langerman, Elena Khramtcova

Publication date: 21 December 2016

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

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

zbMATH Keywords

Voronoi diagram; hierarchical data structure; Hausdorff distance; point location; randomized incremental construction

Mathematics Subject Classification ID

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

68W20: Randomized algorithms

Related Items

On Clustering Induced Voronoi Diagrams, Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Stabbing circles for sets of segments in the plane, Influence-based Voronoi diagrams of clusters

Cites Work

• Unnamed Item
• Unnamed Item
• Farthest-polygon Voronoi diagrams
• Randomized incremental construction of abstract Voronoi diagrams
• A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters
• The upper envelope of piecewise linear functions: Algorithms and applications
• Concrete and abstract Voronoi diagrams
• The upper envelope of Voronoi surfaces and its applications
• A combinatorial property of convex sets
• The nature and meaning of perturbations in geometric computing
• Data structures for halfplane proximity queries and incremental Voronoi diagrams
• Applications of random sampling in computational geometry. II
• The Hausdorff Voronoi diagram of point clusters in the plane
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• Voronoi Diagrams and Delaunay Triangulations
• THE DELAUNAY HIERARCHY
• The L∞ Hausdorff Voronoi Diagram Revisited
• Computing the extreme distances between two convex polygons
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Dynamic Point Location in General Subdivisions
• The Clarkson–Shor Technique Revisited and Extended
• THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH
• Algorithms - ESA 2003