An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments

DOI10.1016/J.COMGEO.2015.11.002MaRDI QIDQ283875zbMATH OpenOpenAlexFDO

Authors Sang Won Bae

Publication date 17 May 2016

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2015.11.002

zbMATH Keywords

line segmentsVoronoi diagrammedial axisweakly simple polygon

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments (extended abstract)
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Constructing the Voronoi diagram of a set of line segments in parallel
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• scientific article; zbMATH DE number 140455

Cites work

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• A sweepline algorithm for Voronoi diagrams
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments (extended abstract)
• An optimal algorithm for intersecting line segments in the plane
• Concrete and abstract Voronoi diagrams
• Detecting weakly simple polygons
• Farthest-polygon Voronoi diagrams
• Finding the medial axis of a simple polygon in linear time
• Medial Axis Transformation of a Planar Shape
• On the computational geometry of pocket machining
• Optimal Search in Planar Subdivisions
• Randomized incremental construction of abstract Voronoi diagrams
• The Voronoi diagram of curved objects
• Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments
• Triangulating a simple polygon in linear time

Cited in

(13)

• An optimal algorithm for computing visible nearest foreign neighbors among colored line segments
• Optimal computation of the Voronoi diagram of disjoint clusters
• The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations. II: Algorithms for constructing Voronoi diagrams based on the theory of optimal set partitioning
• Aspect-ratio Voronoi diagram and its complexity bounds
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments (extended abstract)
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• Convex-straight-skeleton Voronoi diagrams for segments and convex polygons
• Constructing the internal Voronoi diagram of polygonal figure using the sweepline method
• VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
• Robustness of k-gon Voronoi diagram construction
• Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments

This page was built for publication: An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments

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