On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
type: Item
instance of: scholarly article
title: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
zbMATH Open document ID: 1023.65014
DOI: 10.1016/S0925-7721(02)00123-2
author: Mordecai J. Golin
author: Hyeon-Suk Na
published in: Computational Geometry
publication date: 2003-05-27T00:00:00Z
review text: The authors study the complexity (that is, number of vertices, edges and faces) of Voronoi diagrams of points distributed on a 2-dimensional manifold in 3-dimensional space. It is known that the expected complexity for \(n\) points independently and uniformly distributed in a 3-D region is \(O(n)\), but it may be as bad as \(O(n^2)\) if these points lie on a 1-dimensional submanifold. It is proved that for 2-D manifolds the expected complexity is still \(O(n)\). This fact is established for Poisson distribution, although the authors claim that a standard modification allows to extend it to uniform distribution. The proof is very geometrical and nicely illustrated. For detailed proofs of two technical lemmas the reader is referred to a report available on the web.
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1917796
zbMATH Keywords: Voronoi diagrams
zbMATH Keywords: convex polytopes
zbMATH Keywords: random points
zbMATH Keywords: average case analysis
zbMATH Keywords: average complexity
reviewed by: Andrei Martínez Finkelshtein
MaRDI profile type: Publication
cites work: Power Diagrams: Properties, Algorithms and Applications
cites work: Optimal Expected-Time Algorithms for Closest Point Problems
cites work: Higher-dimensional Voronoi diagrams in linear expected time
cites work: The expected number of \(k\)-faces of a Voronoi diagram
cites work: Q3772828
cites work: Nice point sets can have nasty Delaunay triangulations
cites work: Q4003764
cites work: Q3992847
description: scientific article; zbMATH DE number 1917796