A compact piecewise-linear Voronoi diagram for convex sites in the plane
From MaRDI portal
Publication:1907612
DOI10.1007/BF02716580zbMath0840.68119MaRDI QIDQ1907612
M. McAllister, David G. Kirkpatrick, Jack Scott Snoeyink
Publication date: 13 February 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Related Items
Computation of spatial skyline points, Abstract Voronoi diagrams revisited, An optimal algorithm for computing visible nearest foreign neighbors among colored line segments, KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS, Optimal conditions for connectedness of discretized sets, Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties, Hunting Voronoi vertices, Voronoi diagrams for polygon-offset distance functions, Half-plane point retrieval queries with independent and dependent geometric uncertainties, Straight skeletons for general polygonal figures in the plane, Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function, Gathering Asynchronous Robots in the Presence of Obstacles, Euclidean minimum spanning trees with independent and dependent geometric uncertainties, Voronoi diagrams for convex polygon-offset distance functions, Optimizing a constrained convex polygonal annulus, THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC, Divide-and-conquer for Voronoi diagrams revisited, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Convex-straight-skeleton Voronoi diagrams for segments and convex polygons, On the minimum consistent subset problem, Robust Point-Location in Generalized Voronoi Diagrams, Locational optimization problems solved through Voronoi diagrams, Robustness of \(k\)-gon Voronoi diagram construction, The geometry of Minkowski spaces -- a survey. II., Fast tree-based redistancing for level set computations, Semi-Lagrangian methods for level set equations, Tree methods for moving interfaces
Cites Work
- Randomized incremental construction of abstract Voronoi diagrams
- Moving a disc between polygons
- On the construction of abstract Voronoi diagrams
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
- A sweepline algorithm for Voronoi diagrams
- Simplified Voronoi diagrams
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Concrete and abstract Voronoi diagrams
- Applications of random sampling to on-line algorithms in computational geometry
- Fully dynamic Delaunay triangulation in logarithmic expected per operation
- A “retraction” method for planning the motion of a disc
- An Introduction to the Geometry of Numbers
- Optimal Point Location in a Monotone Subdivision
- Computing the extreme distances between two convex polygons
- Optimal Search in Planar Subdivisions
- COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME
- Piecewise linear paths among convex obstacles
- Unnamed Item
- Unnamed Item
- Unnamed Item
