Cheng, Siu-wing; Cheong, Otfried; Everett, Hazel; van Oostrum, René Hierarchical decompositions and circular ray shooting in simple polygons. (English) Zbl 1075.65028 Discrete Comput. Geom. 32, No. 3, 401-415 (2004). A new hierarchical decomposition of a simple polygon is proposed, whose regions have at most three neighbors. The construction of the hierarchy of logarithmic depth and linear size is based on the trapezoidal map (vertical decomposition) of the polygon. As application, circular ray shooting queries in a simple polygon of \(n\) vertices can be answered in \(O\left( \log ^{2}n\right) \) query time, with \(O\left( n\log n\right) \) space and \(O\left( n\log ^{2}n\right) \) preprocessing time, improving over previous results in the literature. A data structure with optimal query time \(O\left( \log n\right) \) and optimal size \(O\left( n\right) \) is obtained for fixed-radius circular ray shooting. Reviewer: Aurelian Bejancu (Safat) Cited in 3 Documents MSC: 65D18 Numerical aspects of computer graphics, image analysis, and computational geometry 52B55 Computational aspects related to convexity Keywords:hierarchical decomposition; data structure; circular ray shooting; polygon PDFBibTeX XMLCite \textit{S.-w. Cheng} et al., Discrete Comput. Geom. 32, No. 3, 401--415 (2004; Zbl 1075.65028) Full Text: DOI