Detecting and decomposing self-overlapping curves

ABSTRACT

Paint one side of a rubber disk black and the other side white; stretch the disk any way you wish in three-dimensional space, subject to the condition that from any point in space, if you look down you see either the white side of the disk or nothing at all. Now make the stretched disk transparent but color its boundary black; project its boundary into a plane that lies below the disk. The resulting curve is self-overlapping. We show how to test whether a given curve is self-overlapping, and how to count how many essentially different stretchings of the disk could give rise to the same curve.

REFERENCES

• A66: L. V. Ahlfors, Complex Analysis, 2d ed., 1966, New York: McGraw-Hill, 114-118.
• CE88: B. Chazelle and H. Edelsbrunner, "An optimal algorithm for intersecting line segments in the plane," Proc. 29th Ann. Symp. on Found. of Comput. Sci., 1988, 590-600.
• dFPP88: Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
• G83: D. H. Greene, "Efficient coding and drawing of planar graphs," 1983, unpublished manuscript.
• LL86: D. T. Lee and A. K. Lin "Generalized Delaunay triangulation for planar graphs," Discrete and Comput. Geom. 1 (1986). 201-217.
• NS80: M. E. Newell and C. H. Sequin, "The inside story on self-intersecting polygons," Lambda 1 (1980). 20-21.
• RT85: P. Rosenstiehl and R. E. Tarjan, "Rectilinear planar layouts and bipolar orientations of planar graphs," Discrete and Comput. Geom. 1 (1986). 343-353.
• W37: H. Whitney, "On regular closed curves in the plane," Compositio Math. 4 (1937). 276-284.

INDEX TERMS

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

General Terms:
Algorithms, Theory