Optimally Cutting a Surface into a Disk

Research output: Contribution to journalArticle

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 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 (g2n log n) time.

Original languageEnglish (US)
Pages (from-to)37-59
Number of pages23
JournalDiscrete and Computational Geometry
Volume31
Issue number1
DOIs
StatePublished - Jan 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Optimally Cutting a Surface into a Disk'. Together they form a unique fingerprint.

  • Cite this