Rectilinear computational geometry
Jörg-Rüdiger Sack · eScholarship@McGill (McGill) · 1984
In this thesis it is demonstrated that the structure of rectilinear polygons can be exploited to solve a variety of geometric problems efficiently. These problems include: (1) recognizing polygonal properties, such as star-shapedness, monotonicity, and edge-visibility, (2) removing hidden lines, (3) constructing the rectilinear convex hull, (4) decomposing rectilinear polygons into simpler components, and (5) placing guards in rectilinear polygons. A new tool for computational geometry is introduced which extracts information about the winding properties of rectilinear polygons. Employing this tool as a preprocessing step, efficient and conceptually clear algorithms for the above problems have been designed.