Higher-dimensional Voronoi diagrams in linear expected time
From MaRDI portal
Publication:804320
DOI10.1007/BF02574694zbMATH Open0727.68128DBLPjournals/dcg/Dwyer91OpenAlexW2097944783WikidataQ56047088 ScholiaQ56047088MaRDI QIDQ804320FDOQ804320
Publication date: 1991
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131163
Recommendations
- Voronoi diagrams in higher dimensions under certain polyhedral distance functions
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
- Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
- The expected number of \(k\)-faces of a Voronoi diagram
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Title not available (Why is that?)
- Voronoi diagrams and arrangements
- Title not available (Why is that?)
- The convex hull of a random set of points
- An Algorithm for Convex Polytopes
- Random Subdivisions of Space into Crystals
- Optimal Expected-Time Algorithms for Closest Point Problems
- Title not available (Why is that?)
- �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II
- �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
- On the convex hull of random points in a polytope
- Sur L'enveloppe convexe des nuages de points aleatoires dans Rn. I
- Title not available (Why is that?)
- Isotropic random simplices
- A faster divide-and-conquer algorithm for constructing Delaunay triangulations
- Delaunay triangulation and the convex hull of n points in expected linear time
- Finding the convex hull facet by facet
- Title not available (Why is that?)
- A new algorithm for three-dimensional Voronoi tessellation
- Construction of Voronoi polyhedra
- A procedure for the construction of Voronoi polyhedra
- Random spheres in a convex body
Cited In (41)
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
- Time-space trade-offs for triangulations and Voronoi diagrams
- The impact of heterogeneity and geometry on the proof complexity of random satisfiability
- The Morse theory of Čech and Delaunay complexes
- Title not available (Why is that?)
- A faster circle-sweep Delaunay triangulation algorithm
- PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS
- Randomized incremental construction of Delaunay triangulations of nice point sets
- The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
- On the randomized construction of the Delaunay tree
- Node-based parallel computing of three-dimensional incompressible flows using the free mesh method
- 3/4-Discrete Optimal Transport
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- On Some Proximity Problems of Colored Sets
- Title not available (Why is that?)
- A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case
- Delaunay-based derivative-free optimization via global surrogates. I: Linear constraints
- Delaunay-based derivative-free optimization via global surrogates. II: Convex constraints
- Title not available (Why is that?)
- Fast multivariate log-concave density estimation
- Incremental topological flipping works for regular triangulations
- On the Complexity of Randomly Weighted Voronoi Diagrams
- Applications of random sampling to on-line algorithms in computational geometry
- The expected number of \(k\)-faces of a Voronoi diagram
- A comparison of sequential Delaunay triangulation algorithms.
- On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
- Moment preserving constrained resampling with applications to particle-in-cell methods
- Persistent homology in \(\ell_\infty\) metric
- A Robust Implementation for Three-Dimensional Delaunay Triangulations
- GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING
- A boundary-partition-based Voronoi diagram of \(d\)-dimensional balls: definition, properties, and applications
- A FEM-BASED MESHFREE METHOD WITH A PROBABILISTIC NODE GENERATION TECHNIQUE
- Title not available (Why is that?)
- A space-time adaptive method for reservoir flows: formulation and one-dimensional application
- Complexity of the Delaunay triangulation of points on polyhedral surfaces
- \textit{OFC}-Delaunay triangulation: a new efficient algorithm for merging two adjacent Delaunay triangulations
- Convergence of Anisotropic Mesh Adaptation via Metric Optimization
- A simple algorithm for higher-order Delaunay mosaics and alpha shapes
- Voronoi diagrams of random lines and flats
- THE DELAUNAY HIERARCHY
This page was built for publication: Higher-dimensional Voronoi diagrams in linear expected time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804320)
