|
|
|
 |
Jeff Erickson
Department of Computer Science
University of Illinois at Urbana-Champaign
Friday, Dec. 10, 11:00am
LC 102, Brooklyn Campus, Polytechnic University
Many geometric problems, such as texture mapping, remeshing,and
morphing, call for a topologically complex surface to be cut into one
or more topological disks. Any orientable surface of genus g can be
cut into a single topological disk by removing a so-called "system of
loops": a set of 2g cycles sharing a common basepoint. I will describe
a simple greedy algorithm based on Dijkstra's shortest-path algorithm
that computes the shortest system of loops with a given basepoint in
O(n log n) time. This solves an open problem of Colin de VerdiĠre and
Lazarus. In fact, our algorithm computes the shortest set of loops
that generate the fundamental group of the surface. It is also
possible to cut a surface into a single disk with a more general graph,
but finding such a cut graph with minimum total length is NP-hard.
This is joint work with Kim Whittlesey, to appear at SODA 2005.
Our paper is available
here.
For further information please contact
Boris Aronov