Randomized incremental construction of abstract Voronoi diagrams

DOI10.1016/0925-7721(93)90033-3zbMath0797.68153OpenAlexW1987221468MaRDI QIDQ685599

Kurt Mehlhorn, Rolf Klein, Stefan Meiser

Publication date: 19 October 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(93)90033-3

zbMATH Keywords

computational geometryabstract Voronoi diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Abstract Voronoi diagram in 3-space ⋮ An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ Abstract Voronoi diagrams revisited ⋮ The L∞ Hausdorff Voronoi Diagram Revisited ⋮ A combinatorial property of convex sets ⋮ A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ Randomized incremental construction of simple abstract Voronoi diagrams in 3-space ⋮ A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM ⋮ Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm ⋮ A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams ⋮ An efficient randomized algorithm for higher-order abstract Voronoi diagrams ⋮ “The big sweep”: On the power of the wavefront approach to Voronoi diagrams ⋮ Voronoi diagrams for polygon-offset distance functions ⋮ Deletion in abstract Voronoi diagrams in expected linear time and related problems ⋮ Fast skeleton construction ⋮ Casting a polyhedron with directional uncertainty ⋮ Forest-like abstract Voronoi diagrams in linear time ⋮ Exact Voronoi diagram of smooth convex pseudo-circles: general predicates, and implementation for ellipses ⋮ PARABOLA SEPARATION QUERIES AND THEIR APPLICATION TO STONE THROWING ⋮ Computing the map of geometric minimal cuts ⋮ COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION ⋮ THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH ⋮ Characterization of contour elements that generate abstract Voronoi diagrams ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Voronoi diagrams for convex polygon-offset distance functions ⋮ THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC ⋮ Divide-and-conquer for Voronoi diagrams revisited ⋮ Randomized incremental construction of simple abstract Voronoi diagrams in 3-space ⋮ A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters ⋮ Maximum spanning trees in normed planes ⋮ Dynamic construction of abstract Voronoi diagrams ⋮ A fast algorithm for data collection along a fixed track ⋮ VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE ⋮ THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs ⋮ Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams ⋮ Deletion in Abstract Voronoi Diagrams in Expected Linear Time. ⋮ The geometry of Minkowski spaces -- a survey. II. ⋮ The predicates of the Apollonius diagram: algorithmic analysis and implementation ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Abstract Voronoi Diagrams from Closed Bisecting Curves ⋮ ABSTRACT VORONOI DIAGRAMS WITH DISCONNECTED REGIONS ⋮ Voronoi diagrams on the sphere ⋮ Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended ⋮ On the complexity of higher order abstract Voronoi diagrams

Uses Software

• Hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the construction of abstract Voronoi diagrams
• Voronoi diagrams and arrangements
• A sweepline algorithm for Voronoi diagrams
• Voronoi diagrams from convex hulls
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Concrete and abstract Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• Applications of random sampling in computational geometry. II
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Power Diagrams: Properties, Algorithms and Applications
• Four results on randomized incremental constructions