The complexity of computing simple circuits in the plane /

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