On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

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)

zbMATH Keywords

average complexityconvex polytopesVoronoi diagramsaverage case analysisrandom points

Mathematics Subject Classification ID

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