Submitted to the
20th Annual ACM-SIAM Symposium on Discrete Algorithms (2009).
Submitted to the
20th Annual ACM-SIAM Symposium on Discrete Algorithms (2009).
![[PDF]](pix/nops.gif){kind=small}
![[PDF]](pix/pdf.gif){kind=small}
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(n2 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)
03 Jul 2007
