Flipping in spirals

摘要

We study the number of edge flips required to transform any triangulation of an n-vertex spiral polygon into any other. We improve the upper bound from 4n - 6 to 3n - 9 flips and show a lower bound of 2n - 8 flips. Instead of using a single canonical triangulation as the intermediate point in the transformation between two triangulations, we use a family of closely-connected triangulations. (C) 2020 Elsevier B.V. All rights reserved.