Next: Problem 39: Distances among Point Sets in \R^2 and \R^3
Previous: Problem 37: Counting Polyominoes
Is it true that every two sets of n planar points in general position with the same number points on their convex hulls have compatible triangulations? Two triangulations are compatible if they have the same combinatorial structure, i.e., if their face lattices are isomorphic. For compatible triangulations T_1 and T_2 of point sets S_1 and S_2, there is a bijection \phi between the points such that ijk is a triangle of T_1 empty of points of S_1 iff \phi(i) \phi(j) \phi(k) is a triangle of T_2 empty of points of S_2.
Open. Conjectured in [AAHK02] to be true.
Morphing.
The answer to the question posed is sometimes no for points not in general position. If the bijection between the points is given and fixed, then compatible triangulations do not always exist [Saa87]. When the bijection is not given, the conjecture is proven only for point sets with at most three points interior to the hull [AAHK02]. Compatible triangulations can always be achieved by the addition of at most a linear number of Steiner points.
triangulations
J. O’Rourke, 1 Jan. 2002.
Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, and Hannes Krasser. Towards compatible triangulations. Theoret. Comput. Sci., ??:??–??, 2002. http://www.cis.TUGraz.at/igi/oaich/.
Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. On compatible triangulations of point sets. In Abstracts 17th European Workshop Comput. Geom., pages 23–26. Freie Universität Berlin, 2001.
A. Saalfeld. Joint triangulations and triangulation maps. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 195–204, 1987.