A linear-time algorithm for computing the Voronoi diagram of a convex polygon

DOI10.1007/BF02187749zbMath0696.68045OpenAlexW2074863496MaRDI QIDQ911267

Alok Aggarwal, Leonidas J. Guibas, Peter W. Shor, James B. Saxe

Publication date: 1989

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

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

zbMATH Keywords

convex polygon convex hull Voronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Related Items

Packing two disks in a polygon, Bumpy pyramid folding, A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Computing the intersection-depth to polyhedra, Compressing spatio-temporal trajectories, Abstract Voronoi diagrams revisited, Star-Unfolding Polygons, Selection and sorting in totally monotone arrays, Voronoi diagrams of moving points in higher dimensional spaces, A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon, Farthest line segment Voronoi diagrams, Two-floodlight illumination of convex polygons, A linear-time construction of the relative neighborhood graph within a histogram, A FAST STRAIGHT-SKELETON ALGORITHM BASED ON GENERALIZED MOTORCYCLE GRAPHS, Resolving Loads with Positive Interior Stresses, DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES, ON DELETION IN DELAUNAY TRIANGULATIONS, A SIMPLE FACTOR-2/3 APPROXIMATION ALGORITHM FOR TWO-CIRCLE POINT LABELING, On selecting a fraction of leaves with disjoint neighborhoods in a plane tree, Voronoi-like partition of lattice in cellular automata, ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM, An optimal algorithm for roundness determination on convex polygons, Algorithms for proximity problems in higher dimensions, Efficient splitting and merging algorithms for order decomposable problems, Vertex removal in two-dimensional Delaunay triangulation: speed-up by low degrees optimization, Deletion in abstract Voronoi diagrams in expected linear time and related problems, Cohesive zone representation and junction partitioning for crystal plasticity analyses, Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Farthest-point Voronoi diagrams in the presence of rectangular obstacles, Forest-like abstract Voronoi diagrams in linear time, Reachability by paths of bounded curvature in a convex polygon, Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem, Base station placement on boundary of a convex polygon, A simple algorithm for higher-order Delaunay mosaics and alpha shapes, Applications of generalized matrix searching to geometric algorithms, Minimizing the diameter of a spanning tree for imprecise points, Unnamed Item, Constrained minimum enclosing circle with center on a query line segment, Maintaining the minimal distance of a point set in polylogarithmic time, Finding the \(k\) smallest spanning trees, Fast algorithms for greedy triangulation, AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS, Computing the shortest diagonal of a monotone polygon in linear time, Fully dynamic Delaunay triangulation in logarithmic expected per operation, Minimizing the sum of diameters efficiently, THE DELAUNAY HIERARCHY, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Efficiently updating constrained Delaunay triangulations, Spanning trees in multipartite geometric graphs, Data structures for halfplane proximity queries and incremental Voronoi diagrams, Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings, Fast greedy triangulation algorithms., Weighted skeletons and fixed-share decomposition, Computing hereditary convex structures, Weighted straight skeletons in the plane, Collision detection algorithm of a continuous type using spherical extreme vertex diagrams, Farthest-point queries with geometric and combinatorial constraints, VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments, Analytical computation of arc menisci configuration under primary drainage in convex capillary cross sections, Optimizing a constrained convex polygonal annulus, Fast algorithms for greedy triangulation, Conformal mapping in linear time, Covering convex polygons by two congruent disks, An optimal algorithm for roundness determination on convex polygons, A simple algorithm for computing the smallest enclosing circle, The geodesic farthest-point Voronoi diagram in a simple polygon, Vector-Based Morphological Operations on Polygons Using Straight Skeletons for Digital Pathology, Delaunay triangulation of imprecise points in linear time after preprocessing, Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time, Assigning weights to minimize the covering radius in the plane, Placing two disks in a convex polygon, Deletion in Abstract Voronoi Diagrams in Expected Linear Time., Reprint of: Weighted straight skeletons in the plane, Efficient splitting and merging algorithms for order decomposable problems., Isoperimetric enclosures, The \(k\)-nearest-neighbor Voronoi diagram revisited, Rapid and accurate computation of the distance function using grids, On computing the optimal bridge between two convex polygons., Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, On optimal bridges between two convex regions, Voronoi Diagrams of Moving Points, IMMOBILIZING A SHAPE, The higher-order Voronoi diagram of line segments

Cites Work