| ABSTRACT Splitting (Complicated) Surfaces Is Hard ∗ (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| Let M be an orientable combinatorial surface without boundary. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus. Specifically, we describe an algorithm to compute the shortest splitting cycle in g O(g) n log n time. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical algorithms and problems—Geometric problems and computations; I.3.5 [Computer Graphics]: Computational geometry and object modeling—Geometric algorithms, languages, | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||