ACM Transactions on Algorithms, 6(4):article 61, 2010.

(Special issue of invited papers from the
19th Annual ACM-SIAM Symposium on Discrete Algorithms)

Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 527-531, 2008.

Abstract:

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, non-contractible, simple cycle on a given orientable combinatorial surface in O(nlogn) time. The only method previously known for this problem was to compute the globally shortest non-contractible or non-separating cycle in O(min{g^{3},n}nlogn) time, where g is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in O(nlogn) time, a tight octagonal decomposition in O(gnlogn) time, and a shortest contractible cycle enclosing a non-empty set of faces in O(nlog^{2}n) time.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012