Optimally cutting a surface into a disk

ABSTRACT

We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.

REFERENCES

• 1: U. Axen and H. Edelsbrunner. Auditory Morse analysis of triangulated manifolds. Mathematical Visualization, 223--236, 1998. Springer-Verlag.
• 2: Chakib Bennis , Jean-Marc Vézien , Gérard Iglésias, Piecewise surface flattening for non-distorted texture mapping, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.237-246, July 1991
• 3: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 4: N. Biggs. Constructions for cubic graphs with large girth. Elec. J. Combin. 5:A1, 1998.
• 5: Johannes Blömer, Computing sums of radicals in polynomial time, Proceedings of the 32nd annual symposium on Foundations of computer science, p.670-677, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185434]
• 6: Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Randomness-Optimal Unique Element Isolation withApplications to Perfect Matching and Related Problems, SIAM Journal on Computing, v.24 n.5, p.1036-1050, Oct. 1995 [doi>10.1137/S0097539793250330]
• 7: T. Dey, H. Edelsbrunner, and S. Guha. Computational topology. Advances in Discrete and Computational Geometry, 109--143, 1999. Contemporary Mathematics 223, American Mathematical Society.
• 8: Tamal K. Dey , Sumanta Guha, Transforming curves on surfaces, Journal of Computer and System Sciences, v.58 n.2, p.297-325, April 1999 [doi>10.1006/jcss.1998.1619]
• 9: T. K. Dey and H. Schipper. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14:93--110, 1995.
• 10: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1:269--271, 1959.
• 11: R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer-Verlag, 1999.
• 12: S. Dreyfus and R. Wagner. The Steiner problem in graphs. Networks 1:195--207, 1971.
• 13: D. Eppstein. Seventeen proofs of Euler's formula: V-E+F=2. The Geometry Junkyard, May 2001. http://www.ics.uci.edu/~eppstein/junkyard/euler/.
• 14: Michael S. Floater, Parametrization and smooth approximation of surface triangulations, Computer Aided Geometric Design, v.14 n.3, p.231-250, April 1997 [doi>10.1016/S0167-8396(96)00031-3]
• 15: G. K. Francis and J. R. Weeks. Conway's ZIP proof. Amer. Math. Monthly 106:393--399, 1999. http://new.math.uiuc.edu/zipproof/.
• 16: M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32:835--859, 1977.
• 17: M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32:826--834, 1977.
• 18: Steven Haker , Sigurd Angenent , Allen Tannenbaum , Ron Kikinis , Guillermo Sapiro , Michael Halle, Conformal Surface Parameterization for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.181-189, April 2000 [doi>10.1109/2945.856998]
• 19: Michael T. Hallett , H. Todd Wareham, A compendium of parameterized complexity results, ACM SIGACT News, v.25 n.3, p.122-123, Sept. 1994 [doi>10.1145/193820.193845]
• 20: M. Hanan. On Steiner's problem with rectilinear distance. SIAM J. Appl. Math. 14:255--265, 1966.
• 21: A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http://www.math.cornell.edu/~hatcher/.
• 22: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 23: Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece [doi>10.1145/380752.380801]
• 24: L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Inform. 15:141--145, 1981.
• 25: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 26: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 27: J. R. Munkres. Topology, 2nd edition. Prentice-Hall, 2000.
• 28: Dan Piponi , George Borshukov, Seamless texture mapping of subdivision surfaces by model pelting and texture blending, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.471-478, July 2000 [doi>10.1145/344779.344990]
• 29: A. Sheffer and E. de Sturler. Surface parameterization for meshing by triangulation flattening. Proc. 9th International Meshing Roundtable, 161--172, 2000. http://www.andrew.cmu.edu/user/sowen/abstracts/Sh742.html.
• 30: J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.
• 31: H. Takahashi and A. Matsuyama. An approximate solution for the network Steiner tree problem. Math. Japonica 24:573--577, 1980.
• 32: W. Thurston. Three-Dimensional Geometry and Topology, Volume 1. Princeton University Press, New Jersey, 1997.
• 33: Gert Vegter, Computational topology, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 34: Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms

Keywords:
NP-hardness, approximation, computational topology, cut graph, polygonal schema, polyhedral 2-manifold