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

DOI10.1007/BF02187890zbMath0628.68042MaRDI QIDQ1093370

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 diagram computational geometry

Mathematics Subject Classification ID

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

Related Items

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, 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

Cites Work