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

Hierarchical decompositions and circular ray shooting in simple polygons

Authors Cheng, Siu-Wing
Cheong, Otfried
Everett, Hazel
Van Oostrum, Rene
Issue Date 2002
Summary A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log2n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).
Language English
Format Technical report
Files in this item:
File Description Size Format
200204.pdf 196140 B Adobe PDF