Connecting Non-intersecting Line Segments into a Simple Polygon (Line)

Sufficient condition to connect line segment set S in the plane into a simple polygonal line is proved．An algorithm is also presented for connecting line segment set S in the plane into a simple polygon．Its basic idea is first to compute the convex hull of line segment set S layer by layer，and change these convex hulls into simple polygons； then compute the points of intersection between polygons，and locally modify the line connections to delete these points of intersection；finally merge some simple polygons into a larger simple polygon．When the number n of line segments in S is large，divide-and conquer algorithm is applied to solve the problem．