next up previous
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 T1 and T2 of point sets S1 and S2, there is a bijection φ between the points such that ijk is a triangle of T1 empty of points of S1 iff φ(i)φ(j)φ(k) is a triangle of T2 empty of points of S2.
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.

Bibliography

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 23-26. Freie Universität Berlin, 2001.

Saa87
A. Saalfeld.
Joint triangulations and triangulation maps.
In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 195-204, 1987.


next up previous
Next: Problem 39: Distances among Up: The Open Problems Project Previous: Problem 37: Counting Polyominoes
The Open Problems Project - December 04, 2015