An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
type: Item
instance of: scholarly article
title: An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
zbMATH Open document ID: 0628.68042
DOI: 10.1007/BF02187890
published in: Discrete \& Computational Geometry
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131029
review text: For two-dimensional Euclidean space, an O(n log n) algorithm for computing the Voronoi diagram of a set of points, line segments, and circular arcs is given. The line and circular segments may intersect only at their endpoints. Possible applications of the algorithm are suggested in robotics.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A37
zbMATH DE Number: 4022640
zbMATH Keywords: computational geometry
zbMATH Keywords: Voronoi diagram
author: Chee K. Yap
MaRDI profile type: Publication
cites work: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
cites work: Q3687711
cites work: Voronoi Diagram in the Laguerre Geometry and Its Applications
cites work: Two-Dimensional Voronoi Diagrams in the L p -Metric
cites work: Medial Axis Transformation of a Planar Shape
cites work: Generalization of Voronoi Diagrams in the Plane
cites work: Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
cites work: Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
cites work: Q3479543
cites work: A “retraction” method for planning the motion of a disc
cites work: Generalized voronoi diagrams for moving a ladder. I: Topological analysis
cites work: Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
cites work: Q4134504
cites work: Intersection and Closest-Pair Problems for a Set of Planar Discs
description: scientific article; zbMATH DE number 4022640