Optimally cutting a surface into a disk

Research output: Contribution to conferencePaper

Abstract

We consider the problem of cutting a set of edges on a poly-hedral 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(g2n log n) time.

Original languageEnglish (US)
Pages244-253
Number of pages10
DOIs
StatePublished - 2002
EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
Duration: Jun 5 2002Jun 7 2002

Other

OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)
CountrySpain
CityBarcelona
Period6/5/026/7/02

Keywords

  • Approximation
  • Computational topology
  • Cut graph
  • NP-hardness
  • Polygonal schema
  • Polyhedral 2-manifold

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Optimally cutting a surface into a disk'. Together they form a unique fingerprint.

Cite this