Randomized incremental construction of abstract Voronoi diagrams

DOI10.1016/0925-7721(93)90033-3MaRDI QIDQ685599zbMATH OpenOpenAlexFDO

Authors Rolf Klein, K. 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 geometryabstract Voronoi diagrams

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 18530
• Randomized incremental construction of Delaunay and Voronoi diagrams
• On the construction of abstract Voronoi diagrams
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• scientific article; zbMATH DE number 177830

Cites work

• scientific article; zbMATH DE number 4149601 (Why is no real title available?)
• scientific article; zbMATH DE number 4110186 (Why is no real title available?)
• scientific article; zbMATH DE number 219277 (Why is no real title available?)
• A sweepline algorithm for Voronoi diagrams
• Applications of random sampling in computational geometry. II
• Applications of random sampling to on-line algorithms in computational geometry
• Concrete and abstract Voronoi diagrams
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Four results on randomized incremental constructions
• On the construction of abstract Voronoi diagrams
• Power Diagrams: Properties, Algorithms and Applications
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoi diagrams and arrangements
• Voronoi diagrams from convex hulls

Cited in

(55)

• VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE
• Voronoi diagrams for polygon-offset distance functions
• PARABOLA SEPARATION QUERIES AND THEIR APPLICATION TO STONE THROWING
• A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Abstract Voronoi diagram in 3-space
• THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS
• On the complexity of higher order abstract Voronoi diagrams
• THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC
• Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Approximation algorithms for polynomial-expansion and low-density graphs
• Faster approximate diameter and distance oracles in planar graphs
• Abstract Voronoi diagrams revisited
• Casting a polyhedron with directional uncertainty
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
• Voronoi diagrams for convex polygon-offset distance functions
• Abstract Voronoi diagrams from closed bisecting curves
• Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• Dynamic construction of abstract Voronoi diagrams
• Randomized incremental construction of Delaunay and Voronoi diagrams
• A fast algorithm for data collection along a fixed track
• scientific article; zbMATH DE number 177830 (Why is no real title available?)
• Maximum spanning trees in normed planes
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• The geometry of Minkowski spaces -- a survey. II.
• Computing the map of geometric minimal cuts
• The overlay of minimization diagrams in a randomized incremental construction
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH
• Computational and structural advantages of circular boundary representation
• Fast skeleton construction
• Abstract Voronoi diagrams with disconnected regions
• Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
• Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
• Incremental Voronoi diagrams
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Computing the Implicit Voronoi Diagram in Triple Precision
• Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams
• A combinatorial property of convex sets
• scientific article; zbMATH DE number 18530 (Why is no real title available?)
• Forest-like abstract Voronoi diagrams in linear time
• Divide-and-conquer for Voronoi diagrams revisited
• Voronoi diagrams on the sphere
• Exact Voronoi diagram of smooth convex pseudo-circles: general predicates, and implementation for ellipses
• “The big sweep”: On the power of the wavefront approach to Voronoi diagrams
• scientific article; zbMATH DE number 1555916 (Why is no real title available?)
• The L∞ Hausdorff Voronoi Diagram Revisited
• Characterization of contour elements that generate abstract Voronoi diagrams

Describes a project that uses

Uses Software

• Hull

This page was built for publication: Randomized incremental construction of abstract Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685599)