Computing the shortest essential cycle

Submitted to Discrete & Computational Geometry, July 2009.

• Download journal submission:

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) 18 Aug 2009