| Computing the Shortest Essential Cycle ∗ (2009) | |||||||||||||||
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 2 log n) time, or in O(n log n) time when both the genus and number of boundaries are fixed. Our result corrects an error in a paper of Erickson and Har-Peled. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||