Computing the shortest essential cycle

Written with Pratik Worah*

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

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 ( 21 Jan 2012