Computing simple circuits from a set of line segments is NP-complete

ABSTRACT

Given a collection of line segments in the plane we would like to connect the segments by their endpoints to construct a simple circuit. (A simple circuit is the boundary of a simple polygon). However, there are collections of line segments where this cannot be done. In this note it is proved that deciding whether a set of line segments admits a simple circuit is NP-complete. Deciding whether a set of horizontal line segments can be connected with horizontal and vertical line segments to construct an orthogonal simple circuit is also shown to be NP-complete.

REFERENCES

• GJT: M. R. Garey, D. S. Johnson, R. E. Tarjan, "The planar Hamiltonian circuit problem is NP-complete," SUM J. Computing, 5,704-714, 1976.
• IPS: A. Itai, C.H. Papadimitriou, J.L. Szwarcliter, "Hamiltonian paths in grid graphs," SIAM J. Compufing, 11 (4), 1982.
• LLRKS: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys, 7&e Traveling Salesman Problem, Wiley, 1985.
• M: David Marr, Vision: A Computational Investigation into the Human Representation and Processing of Visual Information, Henry Holt and Co., Inc., New York, NY, 1982
• O’R: J. O'Rourke, "Uniqueness of orthogonal connect-the-dots," Technical Report Johns Hopkins University, 1986.
• O’RBW: J. O'Rourke, H. Booth, R. Washington, "Connect-the-dots: a new heuristic," Technical Report JHU/EECS&/ll, Johns Hopkins University 1984.
• Rl: D. Rappaport, "On the Complexity of Computing Orthogonal Polygons from a Set of Points," Technical Report TR-SOCS-86.9, McGill University, Aprii 1986.
• R2: David Howard Rappaport, The complexity of computing simple circuits in the plane, 1987
• RIT: D Rappaport , H Imai , G T Toussaint, On computing simple circuits on a set of line segments, Proceedings of the second annual symposium on Computational geometry, p.52-60, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10521]
• RT: P. Rosenstiehl, R. E. Tarjan, "Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations," Discrete & Computational Geomety, 1, 343-353, 1986.
• Tl: G. Toussaint, "Pattern recognition and geometrical complexity," in Proc. 5th Intematiorial Cor#erencc on Pattern Recognition, Miami Beach, pp. 1324-1347, December 1980.
• T2: G. T. Toussaint, "Computational Geometry and Morphology," Technical Report TR-SOCS-86.3, McGill University, February 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Theory