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

DOI10.1007/BF02187890zbMATH Open0628.68042MaRDI QIDQ1093370FDOQ1093370

Authors: Chee K. Yap 

Publication date: 1987

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

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

Recommendations

• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments (extended abstract)
• scientific article; zbMATH DE number 4051001
• An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
• A sweepline algorithm for Voronoi diagrams
• Representing the Voronoï diagram of a simple polygon using rational quadratic Bézier curves

zbMATH Keywords

computational geometryVoronoi diagram

Mathematics Subject Classification ID

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

Cites Work

• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Title not available (Why is that?)
• Medial Axis Transformation of a Planar Shape
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• Generalization of Voronoi Diagrams in the Plane
• Title not available (Why is that?)
• 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
• A “retraction” method for planning the motion of a disc
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Title not available (Why is that?)
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis

Cited In (93)

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

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

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