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

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

Cites work

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

Cited in

(94)

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

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)