Assume that an isomorphism between two n-vertex simple polygons P, Q (with k, l reflex vertices, respectively) is given We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of P and Q. respectively. The first algorithm computes isomorphic triangulations of P and Q by introducing at most O((k + l)2) Steiner points and has running time O(n + (k + l)2). The second algorithm computes isomorphic triangulations of P and Q by introducing at most O(kl) Steiner points and has running time O(n+kl log n). The number of Steiner points introduced by the second algorithm is also worst-case optimal. Unlike the O(n2) algorithm of Aronov, Seidel and Souvaine1 our algorithms are sensitive to the number of reflex vertices of the polygons. In particular, our algorithms have linear running time when k + l ≤ √n for the first algorithm, and kl ≤ n/ log n for the second algorithm.

Additional Metadata
Keywords Isomorphic triangulations, Simple polygons, Steiner points
Journal International Journal of Computational Geometry and Applications
Citation
Kranakis, E, & Urrutia, J. (Jorge). (1999). Isomorphic triangulations with small number of Steiner points. International Journal of Computational Geometry and Applications, 9(2), 171–180.