Home Bookmarks Papers Blog

Optimally Cutting a Surface into a Disk

Jeff Erickson and Sariel Har-Peled

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 nO(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( log2 g)-approximation of the minimum cut graph in O(g2 n log n) time.

Abstract - Postscript, PDF.

@string{DCG    = "Discrete Comput. Geom."}

  author       = "J. Erickson and S. {Har-Peled}",
  title        = "Optimally Cutting a Surface into a Disk",
  journal      = DCG,
  volume       = 31,
  number       = 1,
  pages        = {37--59},
  year         = 2004

Last updated: Mon May 21 11:25:35 CDT 2001