HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item:
Title: Quadtree decomposition, Steiner triangulation, and ray shooting
Authors: Lee, Kam-Hing
Issue Date: 1999
Abstract: We present a new quadtree-based decomposition of a polygon possibly with holes. For a polygon of n vertices, a truncated decomposition can be computed in O(n log n) time which yields a Steiner triangulation of the interior of the polygon that has O(n log n) size and approximates the minimum weight Steiner triangulation (MWST) to within a constant factor. An approximate MWST is good for ray shooting in the average case as defined by Aronov and Fortune. The untruncated decomposition also yields an approximate MWST. Moreover, we show that this triangulation supports query-sensitive ray shooting as defined by Mitchell, Mount, and Suri. Hence, there exists a Steiner triangulation that is simultaneously good for ray shooting in the query-sensitive sense and in the average case.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1999
xvi, 78 leaves : ill. (some col.) ; 30 cm
HKUST Call Number: Thesis COMP 1999 Lee
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat

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