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₁ and T₂ of point sets S₁ and S₂, there is a bijection φ between the points such that ijk is a triangle of T₁ empty of points of S₁ iff φ(i)φ(j)φ(k) is a triangle of T₂ empty of points of S₂.

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.