×

Hierarchical decompositions and circular ray shooting in simple polygons. (English) Zbl 1075.65028

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.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52B55 Computational aspects related to convexity
PDFBibTeX XMLCite
Full Text: DOI