Please use this identifier to cite or link to this item:

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

Authors Golin, Mordecai J.
Na, Hyeon-Suk
Issue Date 2001
Summary It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as ⊝(n2). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution on the surface of a convex polytope.
Language English
Format Technical report
Files in this item:
File Description Size Format
200108.pdf 1488504 B Adobe PDF