Self-overlapping curves revisited

ABSTRACT

Let S be a surface embedded in space in such a way that each point has a neighborhood within which the surface is a terrain. Then S projects to an immersed surface in the plane, the boundary of which is a (possibly self-intersecting) curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a disk embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2^n/2 combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.

REFERENCES

• 1: R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87--90, 1958.
• 2: D. Bennequin. Exemples d'immersions du disque dans le plan qui ne sont pas projections de plongements dans l'espace. C. R. Acad. Sci. Paris Se'r., A-B 281(2--3, AII):A81--A84, 1975.
• 3: W. G. Chinn and N. E. Steenrod. First Concepts of Topology. New Mathematical Library, MAA, 1966.
• 4: C. H. Dowker and M. B. Thistlethwaite. Classification of knot projections. Topology Appl., 16:19--31, 1983.
• 5: D. Eppstein, M. J. van Kreveld, E. Mumford, and B. Speckmann. Edges and switches, tunnels and bridges. In Proc. 10th Worksh. Algorithms and Data Structures, volume 4619 of Lecture Notes in Computer Science, pages 77--88. Springer-Verlag, 2007.
• 6: J. L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, 1962.
• 7: M. L. Marx. Extensions of normal immersions of s¹ into r². Trans. Amer. Math. Soc., 187:309--326, 1974.
• 8: V. Poénaru. Extension des immersions en codimension 1. Séminaire Bourbaki, 10(342):473--505, 1966--1968.
• 9: Peter W. Shor , Christopher J. Van Wyk, Detecting and decomposing self-overlapping curves, Computational Geometry: Theory and Applications, v.2 n.1, p.31-50, Aug. 1992 [doi>10.1016/0925-7721(92)90019-O]
• 10: W. D. Smith , N. C. Wormald, Geometric Separator Theorems and Applications, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.232, November 08-11, 1998
• 11: H. Whitney. On regular closed curves in the plane. Composition Math., 4:276--284, 1937.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics