|
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 |
Size | Format |
|---|
| 200108.pdf | | 1453Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
