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/683
Title: Abstract voronoi diagram in 3-space
Authors: Lê, Ngoc-Minh
Keywords: Voronoi diagrams
Convex distance function
Intersection characteristic
Computational geometry
Issue Date: 1999
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-99-11
Abstract: We propose a class of abstract Voronoi diagrams in 3-space that generalizes the planar abstract Voronoi diagram of Klein. Our class of abstract Voronoi diagrams includes the Voronoi diagram of point sites in general position under any convex distance function. To characterize the abstract Voronoi diagram in 3-space we introduce the notion of intersection characteristic. We determine the intersection characteristic for the simplex, the L, and the Lp distance function. We find that the intersection characteristic in case of the simplex distance function is similar to that of the usual Euclidean distance. This enables us to give a randomized incremental algorithm for computing the Voronoi diagram under the simplex distance function in quadratic expected time.
URI: http://hdl.handle.net/1783.1/683
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
199911.pdf550KbAdobe PDFView/Open

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