TY - GEN

T1 - Tracing compressed curves in triangulated surfaces

AU - Erickson, Jeff G

AU - Nayyeri, Amir

PY - 2012/7/23

Y1 - 2012/7/23

N2 - A simple path or cycle in a triangulated surface is normal if it intersects any triangle in a finite set of arcs, each crossing from one edge of the triangle to another. We describe an algorithm to "trace" a normal curve in O(min{X,n 2 log X}) time, where n is the complexity of the surface triangulation and X is the number of times the curve crosses edges of the triangulation. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in n. Our tracing algorithm computes a new cellular decomposition of the surface with complexity O(n); the traced curve appears as a simple path or cycle in the 1-skeleton of the new decomposition. We apply our abstract tracing strategy to two different classes of normal curves: abstract curves represented by normal coordinates, which record the number of intersections with each edge of the surface triangulation, and simple geodesics, represented by a starting point and direction in the local coordinate system of some triangle. Our normal-coordinate algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer, Sedgwick, and Štefankovic [COCOON 2002, CCCG 2008] and by Agol, Hass, and Thurston [Trans. AMS 2005].

AB - A simple path or cycle in a triangulated surface is normal if it intersects any triangle in a finite set of arcs, each crossing from one edge of the triangle to another. We describe an algorithm to "trace" a normal curve in O(min{X,n 2 log X}) time, where n is the complexity of the surface triangulation and X is the number of times the curve crosses edges of the triangulation. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in n. Our tracing algorithm computes a new cellular decomposition of the surface with complexity O(n); the traced curve appears as a simple path or cycle in the 1-skeleton of the new decomposition. We apply our abstract tracing strategy to two different classes of normal curves: abstract curves represented by normal coordinates, which record the number of intersections with each edge of the surface triangulation, and simple geodesics, represented by a starting point and direction in the local coordinate system of some triangle. Our normal-coordinate algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer, Sedgwick, and Štefankovic [COCOON 2002, CCCG 2008] and by Agol, Hass, and Thurston [Trans. AMS 2005].

KW - Computational topology

KW - Geodesics

KW - Normal coordinates

UR - http://www.scopus.com/inward/record.url?scp=84863956926&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863956926&partnerID=8YFLogxK

U2 - 10.1145/2261250.2261270

DO - 10.1145/2261250.2261270

M3 - Conference contribution

AN - SCOPUS:84863956926

SN - 9781450312998

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 131

EP - 140

BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012

T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012

Y2 - 17 June 2012 through 20 June 2012

ER -