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

DOI10.1007/BF02187749zbMATH Open0696.68045OpenAlexW2074863496MaRDI QIDQ911267FDOQ911267

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

Publication date: 1989

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

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

Recommendations

• scientific article; zbMATH DE number 4051001
• A nearly parallel algorithm for the Voronoi diagram of a convex polygon
• A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
• scientific article; zbMATH DE number 177538
• A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON

zbMATH Keywords

convex hullconvex polygonVoronoi diagram

Mathematics Subject Classification ID

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

Cites Work

• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Title not available (Why is that?)
• Optimal Search in Planar Subdivisions
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Generalized Delaunay triangulation for planar graphs
• A linear algorithm for finding the convex hull of a simple polygon
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

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

This page was built for publication: A linear-time algorithm for computing the Voronoi diagram of a convex polygon

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