Abstract
We describe algorithms to compute the shortest path homotopic to a given path, or the shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface. Unlike earlier results, our algorithms do not require the input path or cycle to be simple. Given a surface with complexity n, genus g ≥ 2, and no boundary, we construct in O(n 2 logn) time a tight octagonal decomposition of the surface - a set of simple cycles, each as short as possible in its free homotopy class, that decompose the surface into a complex of octagons meeting four at a vertex. After the surface is preprocessed, we can compute the shortest path homotopic to a given path of complexity k in O(gnk) time, or the shortest cycle homotopic to a given cycle of complexity k in O(gnk log(nk)) time. A similar algorithm computes shortest homotopic curves on surfaces with boundary or with genus 1. We also prove that the recent algorithms of Colin de Verdìre and Lazarus for shortening embedded graphs and sets of cycles have running times polynomial in the complexity of the surface and the input curves, regardless of the surface geometry.
Original language | English (US) |
---|---|
Pages | 192-201 |
Number of pages | 10 |
State | Published - 2006 |
Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |
Other
Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Miami, FL |
Period | 1/22/06 → 1/24/06 |
ASJC Scopus subject areas
- Software
- General Mathematics