loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Optimal System of Loops on an Orientable Surface
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
Éric Colin de Verdière, Laboratoire d?informatique de l??cole Normale Sup?rieure
Francis Lazarus, Laboratoire IRCOM-SIC
Every compact orientable boundaryless surface M can be cut along simple loops with a common point v0, pairwise disjoint except at v0, so that the resulting surface is a topological disk; such a set of loops is called a fundamental system of loops for M . The resulting disk is a polygon in which the edges are pairwise identified on the surface; it is called a polygonal schema. Assuming that M is triangulated, and that each edge has a given length, we are interested in a shortest (or optimal) system homotopic to a given one, drawn on the vertex-edge graph of M. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give a polynomial (under some reasonable assumptions) algorithm to build such a system. As a byproduct, we get a polynomial algorithm to compute a shortest simple loop homotopic to a given simple loop.
Citation:
Éric Colin de Verdière, Francis Lazarus, "Optimal System of Loops on an Orientable Surface," focs, pp.627, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.