On computing simple circuits on a set of line segments
David D. Rappaport, H Imai, Godfried T. Toussaint · 1986
Given a set of non-intersecting line segments in the plane, we are required to connect the line segments such that they form a simple circuit (a simple polygon).However, not every set of segments can be so connected.Figure 1 shows a set of segments that does not admit a simple circuit.This leads to the challenging problem of determining when a set of segments admits a simple circuit, and if it does, then find such a circuit.It has been shown [Rappaport] that in general, to determine whether a set of segments admits a simple circuit is NP-complete.In this paper an optimal algorithm is presented to determine whether a simple circuit exists, and deliver a simple circuit, on a set of line segments, where each segment has at least one endpoint on the convex hull of the segments (a CHconnected set of segments).Furthermore this technique can be used to determine a simple circuit of minimum length, or a simple circuit that bounds the minimum area, with no increase in computational complexity.The rest of the paper is summarized.In section 2 cf this paper, the preliminary definitions and notation are introduced.In section 3, the geometric properties of the set, of segments are used to transform the segments into an associated graph.