Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time Marcus Schaefer Department of Computer Science DePaul University 243 South Wabash Chicago, Illinois 60604, USA Eric Sedgwick Department of Computer Science DePaul University 243 South Wabash Chicago, Illinois 60604, USA Daniel Sˇtefankovicˇ Department of Computer Science University of Rochester Rochester, New York, USA December 3, 2007 Abstract Simple curves on surfaces are often represented as sequences of intersections with a trian- gulation.
- recent developments of algorithms over free monoids
- polynomial time algorithms
- intersection sequence
- isotopy rel boundary
- slp
- components
- length
- surface
- size
- time