Computing the shortest essential cycle

Written with Pratik Worah*

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


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