Computing simple circuits from a set of line segments

David Rappaport, Hiroshi Imai, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


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 an O(n log n)-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.

Original languageEnglish (US)
Pages (from-to)289-304
Number of pages16
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing simple circuits from a set of line segments'. Together they form a unique fingerprint.

Cite this