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/724
Title: Quadtree, ray shooting and approximate minimum weight steiner triangulation
Authors: Cheng, Siu-Wing
Lee, Kam-Hing
Keywords: Minimum weight Steiner triangulation
Ray shooting
Algebraic decision tree model
Issue Date: 2001
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2001-01
Abstract: We present a quadtree-based decomposition of the interior of a polygon with holes. The complete decomposition yields a constant factor approximation of the minimum weight Steiner triangulation (MWST) of the polygon. We show that this approximate MWST supports ray shooting queries in the query-sensitive sense as defined by Mitchell, Mount and Suri. A proper truncation of our quadtree-based decomposition yields another constant factor approximation of the MWST. For a polygon with n vertices, the complexity of this approximate MWST is O(n log n) and it can be constructed in O(n log n) time. The running time is optimal in the algebraic decision tree model.
URI: http://hdl.handle.net/1783.1/724
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200101.pdf250KbAdobe PDFView/Open

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