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:
Title: Hierarchical decompositions and circular ray shooting in simple polygons
Authors: Cheng, Siu-Wing
Cheong, Otfried
Everett, Hazel
Van Oostrum, Rene
Keywords: Hierarchical decomposition
Simple polygon
Circular ray shooting
Issue Date: 2002
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2002-04
Abstract: 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).
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200204.pdf191KbAdobe PDFView/Open

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