Computing simple circuits from a set of line segments |
| |
| Authors: | David Rappaport Hiroshi Imai Godfried T. Toussaint |
| |
| Affiliation: | (1) Department of Computing and Information Science, Queen's University, K7L 3N6 Kingston, Ontario, Canada;(2) Department of Computer Science and Communication Engineering, Faculty of Engineering, Kyushu University, 812 Hakozaki, Fukuoka, Japan;(3) School of Computer Science, McGill University, 805 Sherbrooke Street West, H3A 2K6 Montreal, Quebec, Canada |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
