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

DOI10.1007/s00453-016-0118-yzbMath1352.68265arXiv1312.3904OpenAlexW1481203752MaRDI 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 diagramhierarchical data structureHausdorff distancepoint locationrandomized incremental construction

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (5)

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

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

This page was built for publication: A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters