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