Randomized incremental construction of abstract Voronoi diagrams

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

Rolf Klein, Kurt Mehlhorn, 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 geometry; abstract Voronoi diagrams

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

Related Items

A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM, PARABOLA SEPARATION QUERIES AND THEIR APPLICATION TO STONE THROWING, VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE, THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS, THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH, Voronoi diagrams for convex polygon-offset distance functions, Characterization of contour elements that generate abstract Voronoi diagrams, Abstract Voronoi diagrams revisited, Divide-and-conquer for Voronoi diagrams revisited, Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm, A combinatorial property of convex sets, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, Casting a polyhedron with directional uncertainty, Voronoi diagrams on the sphere, Abstract Voronoi diagram in 3-space, A compact piecewise-linear Voronoi diagram for convex sites in the plane, Dynamic construction of abstract Voronoi diagrams, The geometry of Minkowski spaces -- a survey. II., The predicates of the Apollonius diagram: algorithmic analysis and implementation, THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC

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