On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
From MaRDI portal
Publication:1873689
DOI10.1016/S0925-7721(02)00123-2zbMath1023.65014MaRDI QIDQ1873689
Mordecai J. Golin, Hyeon-Suk Na
Publication date: 27 May 2003
Published in: Computational Geometry (Search for Journal in Brave)
Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)
Related Items (12)
Practical distribution-sensitive point location in triangulations ⋮ The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ A tight bound for the Delaunay triangulation of points on a polyhedron ⋮ A simple algorithm for higher-order Delaunay mosaics and alpha shapes ⋮ Complexity of the Delaunay triangulation of points on polyhedral surfaces ⋮ Union of Hypercubes and 3D Minkowski Sums with Random Sizes. ⋮ Unnamed Item ⋮ Union of hypercubes and 3D Minkowski sums with random sizes ⋮ Power particles ⋮ Randomized incremental construction of Delaunay triangulations of nice point sets ⋮ An efficient trivariate algorithm for tetrahedral Shepard interpolation ⋮ Generating random points (or vectors) controlling the percentage of them that are extreme in their convex (or positive) hull
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Higher-dimensional Voronoi diagrams in linear expected time
- The expected number of \(k\)-faces of a Voronoi diagram
- Optimal Expected-Time Algorithms for Closest Point Problems
- Power Diagrams: Properties, Algorithms and Applications
- Nice point sets can have nasty Delaunay triangulations
This page was built for publication: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
