Isomorphic Triangulation of Simple Polygons Diana Garroway 
  Introduction | Definitions | Algorithm | Applet | History/Links


History

[1989]       Jacob Goodman & Richard Pollock propose the problem.   It is, as stated in [1]:  "Is it possible to triangulate any two polygons with the same number of vertices compatibaly if additional vertices are allowed in the interior?  If yes, how many of such points are required? "

[1993]       Boris Aronov, Raimond Seidel & Diane Souvaine [1] prove that the answer to the problem is “yes” and Ω(n2) extra points are sometimes required.  They propose an algorithm called the universal triangulation algorithm that runs in O(n2).

[1994]       Evangelos Kranakis & Jorge Urrutia [2] present an algorithm that runs in O(n + r2) and introduces at most O(r2) extra points, where r is the total number of reflex vertices in the two polygons.

[1997]       Himanshu Gupta & Rephael Wenger [3] present an algorithm that minimizes the number of triangles in the end triangulations.  It runs in O(M log n + n log2 n) where M is the optimal number of triangles.

[2001]       Craig Gotsman & Vitaly Surazhsky [4] present a modification on the algorithm of Aronov et al, that takes advantage of a reduced spiderweb connectivity inorder to reduce the
number of stiener points that are required.  The algorithm is O(n2). 

[2002]       Craig Gotsman & Vitaly Surazhsky [5] present an algorithm that solves a major flaw of all preceding algorithms (it doesn’t introduce extra points if they are not necessary), but runs in O(n4 log n).

Bibliography (with links)

1. B. Aronov, R. Seidel, and D.L. Souvaine, On compatible triangulations of simple polygons,  Computational Geometry: Theory and Applications, 3:27-35, 1993

2. E. Kranakis and J. Urrutia, Isomorphic triangulations with small number of Steiner points, International Journal of Computational Geometry and Applications, 9(2):171-180, 1999.

3. H. Gupta and R. Wenger, Constructing piecewise linear homeomorphisms of simple polygons, J. Algorithms, 22(1):142-157, 1997.

4. V. Surazhsky and C. Gotsman,  Guaranteed intersection-free polygon morphing,  Computers and Graphics, 25(1):67-75, 2001.

5.  V. Surazhsky and C. Gotsman, High Quality Compatible Triangulations,  Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp. 183-192, Sept. 15-18 2002.