Greedy optimal homotopy and homology generators

Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 1038–1046 2005.

• Download SODA version:
  
• Download presentation (36 slides): Keynote archive, exported PPT, color PDF, b/w 4up PDF

Abstract:

We describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed coefficient field) of any oriented 2-manifold. In particular, we show that the shortest set of loops that generate the fundamental group of any oriented combinatorial 2-manifold, with any given basepoint, can be constructed in O(n log n) time using a straightforward application of Dijkstra's shortest path algorithm. This solves an open problem of Colin de Verdière and Lazarus.

In memory of John R B Whittlesey (1927-2003)

Note: Since this paper appeared, Éric Colin de Verdière discovered a considerably simpler proof that the greedy system of loops is optimal.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012