Optimally cutting a surface into a disk
| dc.creator | Erickson, Jeff | |
| dc.creator | Har-Peled, Sariel | |
| dc.date | 2002-07-02 | |
| dc.date.accessioned | 2026-07-07T03:18:34Z | |
| dc.date.available | 2026-07-07T03:18:34Z | |
| dc.description | 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 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(log^2 g)-approximation of the minimum cut graph in O(g^2 n log n) time. | |
| dc.description | 24 pages, 6 figures; full version of SOCG 2002 paper; see also http://www.cs.uiuc.edu/~jeffe/pubs/schema.html | |
| dc.identifier | https://arxiv.org/abs/cs/0207004 | |
| dc.identifier | http://arxiv.org/abs/cs/0207004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31164 | |
| dc.subject | Computational Geometry | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Graphics | |
| dc.subject | F.2.2; I.3.5; G.2.m | |
| dc.title | Optimally cutting a surface into a disk | |
| dc.type | text |