Complexity for billiards in regular N-gons

We compute the complexity of the billiard language of the regular Euclidean $N$-gons (and other families of rational lattice polygons), answering a question posed by Cassaigne-Hubert-Troubetzkoy. Our key technical result is a counting result for saddle connections on lattice surfaces, when we count by combinatorial length.