Hierarchical decompositions and circular ray shooting in simple polygons (Q705130)

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.