An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments

DOI10.1007/BF02187890zbMath0628.68042MaRDI QIDQ1093370

Chee-Keng Yap

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131029

zbMATH Keywords

Voronoi diagramcomputational geometry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other problems of combinatorial convexity (52A37)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• A “retraction” method for planning the motion of a disc
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Generalization of Voronoi Diagrams in the Plane
• Medial Axis Transformation of a Planar Shape

Related Items (85)

2-point site Voronoi diagrams ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ Voronoi diagrams over dynamic scenes ⋮ Representation of segment Voronoi diagram by Bézier curves ⋮ The Offset Filtration of Convex Objects ⋮ An optimal algorithm for computing visible nearest foreign neighbors among colored line segments ⋮ Farthest line segment Voronoi diagrams ⋮ Computing the smallest k-enclosing circle and related problems ⋮ A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects ⋮ Finding a closet visible vertex pair between two polygons ⋮ Coordinated motion planning for two independent robots ⋮ A straightforward algorithm for computing the medial axis of a simple polygon ⋮ Exploiting curvatures to compute the medial axis for domains with smooth boundary ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ On fast planning of suboptimal paths amidst polygonal obstacles in plane ⋮ On the geodesic Voronoi diagram of point sites in a simple polygon ⋮ Witness Gabriel graphs ⋮ Voronoi-like partition of lattice in cellular automata ⋮ A survey of motion planning and related geometric algorithms ⋮ Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Hunting Voronoi vertices ⋮ Approximate matching of polygonal shapes ⋮ Degenerate point/curve and curve/curve bisectors arising in medial axis computations for planar domains with curved boundaries ⋮ Improved algorithms for the farthest colored Voronoi diagram of segments ⋮ A plane-sweep algorithm for finding a closest pair among convex planar objects ⋮ Computing constrained minimum-width annuli of point sets ⋮ Deconstructing approximate offsets ⋮ Revisiting Hyperbolic Voronoi Diagrams in Two and Higher Dimensions from Theoretical, Applied and Generalized Viewpoints ⋮ How to cut corners and get bounded convex curvature ⋮ PRECISE VORONOI CELL EXTRACTION OF FREE-FORM PLANAR PIECEWISE C¹-CONTINUOUS CLOSED RATIONAL CURVES ⋮ OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS ⋮ Fast skeleton construction ⋮ Multi-robot motion planning for unit discs with revolving areas ⋮ Straight skeletons for general polygonal figures in the plane ⋮ On computing the convex hull of (piecewise) curved objects ⋮ BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS ⋮ Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function ⋮ Fixed-radius near neighbors search algorithms for points and segments ⋮ On maximum flows in polyhedral domains ⋮ Bold graph drawings ⋮ Maximizing Voronoi regions of a set of points enclosed in a circle with applications to facility location ⋮ An axiomatic approach to Voronoi-diagrams in 3D ⋮ Deferred data structure for the nearest neighbor problem ⋮ A convex hull algorithm for discs, and applications ⋮ An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles ⋮ COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION ⋮ Characterization of contour elements that generate abstract Voronoi diagrams ⋮ A convex polygon among polygonal obstacle: Placement and high-clearance motion ⋮ Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments ⋮ Constructing the Voronoi diagram of a set of line segments in parallel ⋮ Duality of constrained Voronoi diagrams and Delaunay triangulations ⋮ The upper envelope of Voronoi surfaces and its applications ⋮ Disk packing for the estimation of the size of a wire bundle ⋮ Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology ⋮ VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments ⋮ Largest bounding box, smallest diameter, and related problems on imprecise points ⋮ Divide-and-conquer for Voronoi diagrams revisited ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Conformal mapping in linear time ⋮ Convex-straight-skeleton Voronoi diagrams for segments and convex polygons ⋮ Computing the cut locus, Voronoi diagram, and signed distance function of polygons ⋮ Constructing the internal Voronoi diagram of polygonal figure using the sweepline method ⋮ Near optimal minimal convex hulls of disks ⋮ Low complexity algorithms for optimal consumer push-pull partial covering in the plane ⋮ Moving a disc between polygons ⋮ Robust Construction of the Additively-Weighted Voronoi Diagram via Topology-Oriented Incremental Algorithm ⋮ Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams ⋮ Locational optimization problems solved through Voronoi diagrams ⋮ Empty pseudo-triangles in point sets ⋮ A transfinite form of Sibson's interpolant ⋮ Convex hull of a planar set of straight and circular line segments ⋮ Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. II: Detailed algorithm description ⋮ Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. I: Theoretical foundations ⋮ Fast tree-based redistancing for level set computations ⋮ Semi-Lagrangian methods for level set equations ⋮ Tree methods for moving interfaces ⋮ Rapid and accurate computation of the distance function using grids ⋮ Stable Computation of the 2D Medial Axis Transform ⋮ Specified–Precision Computation of Curve/Curve Bisectors ⋮ IMMOBILIZING A SHAPE ⋮ Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks ⋮ On soft predicates in subdivision motion planning ⋮ The bisector of a point and a plane parametric curve

This page was built for publication: An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments