Next: Problem 39: Distances among
Up: The Open Problems Project
Previous: Problem 37: Counting Polyominoes
Problem 38: Compatible Triangulations
 Statement
 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
φ between the points such that ijk
is a triangle of T_{1} empty of points of S_{1} iff
φ(i)φ(j)φ(k)
is a triangle of T_{2} empty of points of S_{2}.
 Origin
 [AAK01] and [AAHK02].
 Status/Conjectures
 Open.
Conjectured in [AAHK02] to be true.
 Motivation
 Morphing.
 Partial and Related Results
 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.
 Categories
 triangulations
 Entry Revision History
 J. O'Rourke, 1 Jan. 2002.
 AAHK02

Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, and Hannes Krasser.
Towards compatible
triangulations.
Theoret. Comput. Sci., ??:????, 2002.
http://www.cis.TUGraz.at/igi/oaich/.
 AAK01

Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser.
On compatible triangulations of point sets.
In Abstracts 17th European Workshop Comput. Geom., pages
2326. Freie Universität Berlin, 2001.
 Saa87

A. Saalfeld.
Joint triangulations and triangulation maps.
In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 195204,
1987.
Next: Problem 39: Distances among
Up: The Open Problems Project
Previous: Problem 37: Counting Polyominoes
The Open Problems Project  December 04, 2015