Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/728
On the average complexity of 3DVoronoi diagrams of random points on convex polytopes
Authors 
Golin, Mordecai J.
Na, HyeonSuk 


Issue Date  2001  
Summary  It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3dimensional Voronoi diagram of n points can be as bad as ⊝(n^{2}). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3dimensional 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 2dimensional region in 3dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution on the surface of a convex polytope.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
