Please use this identifier to cite or link to this item:

Quadtree, ray shooting and approximate minimum weight steiner triangulation

Authors Cheng, Siu-Wing
Lee, Kam-Hing
Issue Date 2001
Summary 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.
Language English
Format Technical report
Files in this item:
File Description Size Format
200101.pdf 256430 B Adobe PDF