ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187791
Permalink