The Complexity of Computing Simple Circuits in the Plane
- ISBN-10
- 0315381566
- ISBN-13
- 9780315381568
- Pages
- 96
- Language
- English
- Published
- 1986
- Publisher
- Thesis (Ph.D.)--McGill University
- Author
- David Rappaport
Description
"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."--
