HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/728
Title: On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
Authors: Golin, Mordecai J.
Na, Hyeon-Suk
Keywords: 3-dimensional Voronoi diagram
2-dimensional region
3-dimensional space
Issue Date: 2001
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2001-08
Abstract: 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.
URI: http://hdl.handle.net/1783.1/728
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200108.pdf1453KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.