As far back as Euclid's ruler and compass constructions, computation and geometry have been domains for the exploration and development of fundamental mathematical concepts and ideas. The invention of computers has spurred new research in computation, and now with a variety of applications couched in the fundamentals of Euclidean geometry, the study of geometric algorithms has again become a popular mathematical pursuit. / In this thesis, the computational aspects of a fundamental problem in Euclidean geometry is examined. Given a set of line segments in the Euclidean plane, one is asked to connect all the segments to form a simple closed circuit. It is shown that for some sets of line segments it is impossible to perform this task. The problem of deciding whether a set of line segments admits a simple circuit is proved to be NP-complete. A restriction of the class of permissible input allows a polynomial time solution to the simple circuit decision problem. It is also shown that a polynomial solution can be realized by restricting the class of simple circuit in the output. All the polynomial time decision algorithms exhibited deliver a simple circuit if one exists. Furthermore, in all cases the simple circuit obtained can be optimized with respect to area or perimeter.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.75339 |
| Date | January 1986 |
| Creators | Rappaport, David, 1955- |
| 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: 000414924, proquestno: AAINL38156, Theses scanned by UMI/ProQuest. |
Page generated in 0.0027 seconds