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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.71872 |
| Date | January 1984 |
| Creators | Sack, Jörg-Rüdiger. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 000216762, proquestno: AAINK66605, Theses scanned by UMI/ProQuest. |
Page generated in 0.0024 seconds