Randomized incremental construction of Delaunay and Voronoi diagrams

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

zbMATH Keywords

randomized algorithm Voronoi diagrams Delaunay triangulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

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