Home | Bookmarks | Papers | Blog |

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

Abstract - Postscript, PDF.

@string{DCG = "Discrete Comput. Geom."} @article{eh-ocsid-04, 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