Randomized incremental construction of abstract Voronoi diagrams

DOI10.1016/0925-7721(93)90033-3zbMATH Open0797.68153OpenAlexW1987221468MaRDI QIDQ685599FDOQ685599

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

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

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)

Cites Work

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

Cited In (55)

• PARABOLA SEPARATION QUERIES AND THEIR APPLICATION TO STONE THROWING
• Voronoi diagrams for polygon-offset distance functions
• A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• THE ANCHORED VORONOI DIAGRAM: STATIC, DYNAMIC VERSIONS AND APPLICATIONS
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Abstract Voronoi diagram in 3-space
• 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
• Voronoi diagrams for convex polygon-offset distance functions
• Abstract Voronoi diagrams revisited
• Casting a polyhedron with directional uncertainty
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
• 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
• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Dynamic construction of abstract Voronoi diagrams
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Title not available (Why is that?)
• A fast algorithm for data collection along a fixed track
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• Maximum spanning trees in normed planes
• 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
• Fast skeleton construction
• Computational and structural advantages of circular boundary representation
• 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
• Forest-like abstract Voronoi diagrams in linear time
• Title not available (Why is that?)
• Voronoi diagrams on the sphere
• Divide-and-conquer for Voronoi diagrams revisited
• 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
• Title not available (Why is that?)
• The L∞ Hausdorff Voronoi Diagram Revisited
• Characterization of contour elements that generate abstract Voronoi diagrams
• VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE

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)