Optimally cutting a surface into a disk

Details Optimally cutting a surface into a disk Optimally cutting a surface into a disk

2002-07-02

arxiv.org/abs/cs/0207004v1

Computer Science

Computational Geometry

24 pages, 6 figures; full version of SOCG 2002 paper; see also http://www.cs.uiuc.edu/~jeffe/pubs/schema.html

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimally cutting a surface into a disk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimally cutting a surface into a disk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimally cutting a surface into a disk will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-526140