Carleton University
Technical Report TR-257
December 1994
Isomorphic Triangulations with Minimal Number of Steiner Points
Evangelos Kranakis & Jorge Urrutia
Abstract
We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of two simple n vertex polygons P,Q with k, l reflex vertices, respectively. The first algorithm computes an isomorphism by introducing at most O((k + l)2) Steiner points and has running time O(n + (k + l)2). The second algorithm computes an isomorphism 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 optimal. This solves an open problem first proposed by Goodman and Pollack and subsequently elaborated by Aronov, Seidel and Souvaine (see [1]).