``The big sweep: On the power of the wavefront approach to Voronoi diagrams

DOI10.1007/BF02523236MaRDI QIDQ2365174zbMATH OpenFDO

Authors Frank Dehne, Rolf Klein

Publication date 22 June 1997

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02523236

zbMATH Keywords

Delaunay triangulationnice metricssweeplineVoronoi diagrams

Mathematics Subject Classification ID

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

Recommendations

• “The big sweep”: On the power of the wavefront approach to Voronoi diagrams
• A sweepline algorithm for Voronoi diagrams
• scientific article; zbMATH DE number 4060717
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments (extended abstract)
• Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
• The probabilistic complexity of the Voronoi diagram of points on a polyhedron
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
• Divide-and-conquer for Voronoi diagrams revisited

Cites work

• A sweepline algorithm for Voronoi diagrams
• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• Applications of random sampling in computational geometry. II
• Concrete and abstract Voronoi diagrams
• scientific article; zbMATH DE number 4060214 (Why is no real title available?)
• scientific article; zbMATH DE number 4060717 (Why is no real title available?)
• scientific article; zbMATH DE number 4110186 (Why is no real title available?)
• scientific article; zbMATH DE number 403949 (Why is no real title available?)
• On the construction of abstract Voronoi diagrams
• Some dynamic computational geometry problems
• Voronoi diagrams and arrangements
• Voronoi diagrams from convex hulls

Cited in

(9)

• Voronoi diagram for services neighboring a highway
• Robustness of k-gon Voronoi diagram construction
• Voronoi diagrams on orbifolds
• On location-allocation problems for dimensional facilities
• The L∞ Hausdorff Voronoi Diagram Revisited
• Computing the map of geometric minimal cuts
• “The big sweep”: On the power of the wavefront approach to Voronoi diagrams
• VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE
• A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions

This page was built for publication: ``The big sweep: On the power of the wavefront approach to Voronoi diagrams

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