Tracing Compressed Curves in Triangulated Surfaces

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. A normal curve is a finite set of disjoint normal paths and normal cycles. We describe an algorithm to "trace" a normal curve in O(min {X, n²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 in the 1-skeleton of the new decomposition as a set of simple disjoint paths and cycles. 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 et al. (Proceedings of 8th International Conference Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387, pp. 370-380. Springer, Berlin 2002; Proceedings of 20th Canadian Conference on Computational Geometry, pp. 111-114, 2008) and by Agol et al. (Trans Am Math Soc 358(9): 3821-3850, 2006).