Isomorphic Triangulation of Simple Polygons  Diana Garroway  

[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 Ω(n^{2}) extra points are sometimes required. They propose an algorithm called the universal
triangulation algorithm that runs in O(n^{2}).
[1994] Evangelos Kranakis & Jorge
Urrutia [2] present an algorithm that runs
in O(n + r^{2}) and introduces at most O(r^{2})
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 log^{2} 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(n^{2}).
[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(n^{4} 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:2735, 1993
2.
E. Kranakis and J. Urrutia, Isomorphic
triangulations with small number of Steiner points, International
Journal of Computational Geometry and Applications, 9(2):171180, 1999.
3.
H. Gupta and R. Wenger, Constructing
piecewise linear homeomorphisms of simple polygons, J.
Algorithms, 22(1):142157, 1997.
4.
V. Surazhsky and C. Gotsman, Guaranteed
intersectionfree polygon morphing, Computers and
Graphics, 25(1):6775, 2001.
5. V. Surazhsky and C. Gotsman, High Quality Compatible Triangulations, Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp. 183192, Sept. 1518 2002.