Computing the shortest essential cycle

Discrete & Computational Geometry 44(4):912–930, 2010.

• Download journal version (final except for copy-editing):

Abstract:

An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable combinatorial surface in O(n² log n) time, or in O(n log n) time when the genus and number of boundaries is fixed. Our result corrects an error in a paper of Erickson and Har-Peled.

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