Randomized incremental construction of Delaunay and Voronoi diagrams
From MaRDI portal
Publication:1185289
DOI10.1007/BF01758770zbMath0743.68128OpenAlexW2057512681WikidataQ56047092 ScholiaQ56047092MaRDI QIDQ1185289
Micha Sharir, Donald E. Knuth, Leonidas J. Guibas
Publication date: 28 June 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758770
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (57)
A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis ⋮ Computing a single cell in the overlay of two simple polygons ⋮ Expected time analysis for Delaunay point location ⋮ Edge insertion for optimal triangulations ⋮ HCPO: an efficient insertion order for incremental Delaunay triangulation ⋮ Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand ⋮ An introduction to randomization in computational geometry ⋮ Computing the Implicit Voronoi Diagram in Triple Precision ⋮ Tensile Structure Form-Finding on the Basis of Properties of Frame-Grid Template ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ Incremental topological flipping works for regular triangulations ⋮ On-line construction of the upper envelope of triangles and surface patches in three dimensions ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ Spatially-decaying aggregation over a network ⋮ Randomized geometric algorithms and pseudorandom generators ⋮ Queries on Voronoi diagrams on moving points ⋮ Splat representation of parametric surfaces ⋮ Some numerical issues on the use of XFEM for ductile fracture ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ A faster circle-sweep Delaunay triangulation algorithm ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ Remarks on the computation of the horizon of a digital terrain ⋮ Parallel computation of alpha complexes for biomolecules ⋮ Unnamed Item ⋮ Voronoi diagram with visual restriction ⋮ Unnamed Item ⋮ Fixed-radius near neighbors search ⋮ Markov incremental constructions ⋮ An upper bound for conforming Delaunay triangulations ⋮ Randomized incremental construction of abstract Voronoi diagrams ⋮ Four results on randomized incremental constructions ⋮ THE DELAUNAY HIERARCHY ⋮ A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions ⋮ A comparison of sequential Delaunay triangulation algorithms. ⋮ On the randomized construction of the Delaunay tree ⋮ Fast reconstruction of Delaunay triangulations ⋮ Quantitative evaluation of multiple-point simulations using image segmentation and texture descriptors ⋮ COMPACT REPRESENTATIONS OF SIMPLICIAL MESHES IN TWO AND THREE DIMENSIONS ⋮ Flip Algorithm for Segment Triangulations ⋮ THE SHUFFLING BUFFER ⋮ ADAPTIVE SIMPLICIAL GRIDS FROM CROSS-SECTIONS OF MONOTONE COMPLEXES ⋮ Adaptive dynamic cohesive fracture simulation using nodal perturbation and edge-swap operators ⋮ On lazy randomized incremental construction ⋮ A fast algorithm for the alpha-connected two-center decision problem ⋮ Density-Based Clustering Based on Topological Properties of the Data Set ⋮ Effect of Elevated Temperature on Concrete Structures by Discontinuous Boundary Element Method ⋮ A unified approach to tail estimates for randomized incremental construction ⋮ Simplicial complex with approximate rotational symmetry: a general class of simplicial complexes ⋮ An applied point pattern matching problem: Comparing 2D patterns of protein spots ⋮ Fast dynamic grid deformation based on Delaunay graph mapping ⋮ Grid generation and optimization based on centroidal Voronoi tessellations ⋮ \(k\)-sets and random hulls ⋮ Regular triangulations of dynamic sets of points ⋮ Approximating Voronoi Diagrams of Convex Sites in Any Dimension ⋮ Dog Bites Postman
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the construction of abstract Voronoi diagrams
- A sweepline algorithm for Voronoi diagrams
- A combinatorial result about points and balls in Euclidean space
- Circles through two points that always enclose many points
- Applications of random sampling in computational geometry. II
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Optimal Point Location in a Monotone Subdivision
- Optimal Expected-Time Algorithms for Closest Point Problems
- Optimal Search in Planar Subdivisions
- Computing Dirichlet Tessellations in the Plane
- A note on Delaunay diagonal flips
- A fast planar partition algorithm, II
This page was built for publication: Randomized incremental construction of Delaunay and Voronoi diagrams
