A Combinatorial Upper Bound on the Length of Twang Cascades


Damian et al. introduced an intuitive type of transformations between simple polygons on a finite set of points in the plane. Each transformation consists of a sequence of atomic modifications of two types, called stretches and twangs. They proved that, for a given set of n points, the space of these simple polygons is connected by $O(n^2)$ such transformations. We solve an open question of Damian et al. concerning a combinatorial upper bound on the length of these sequences. To this end, we show that the length of a twang cascade is bounded by $n^3/2$.

European Workshop on Computational Geometry (EuroCG'17)