Abstract
We consider the problem of cutting a subset of the edges of 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 in general, 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(log2 g)-approximation of the minimum cut graph in O(g 2 n log n) time.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Erickson, J., Har-Peled, S. Optimally Cutting a Surface into a Disk. Discrete Comput Geom 31, 37–59 (2004). https://doi.org/10.1007/s00454-003-2948-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-003-2948-z