Compatible Triangulations
For an integer , let be finite sets, each of size , with no three points collinear. Let be the number of vertices of the convex hull of , and assume . A triangulation of is a maximal noncrossing straight-line graph with vertex set ; its bounded faces are triangles. Is it always possible to choose triangulations whose face lattices are isomorphic? Equivalently, is there a bijection such that, for every three distinct points , is a triangular face of if and only if is a triangular face of ? Since the point sets are in general position, these faces are empty of other points of their respective sets. Open Problems Project, Problem 38
Background
Compatible triangulations are useful in morphing: they give two point-set triangulations with the same abstract structure, allowing the regions bounded by their convex hulls to be transformed while preserving planarity. The problem has a related antecedent in Saalfeld’s 1987 work on joint triangulations and triangulation maps. Aichholzer, Aurenhammer, Hurtado, and Krasser formulated the conjecture that matching the numbers of convex-hull vertices suffices; their work appeared in the early 2000s. Open Problems Project, Problem 38 Some Counterexamples for Compatible Triangulations (arXiv:1612.04861) Aichholzer et al., Towards Compatible Triangulations
The hull-size condition is necessary: a triangulation of a set of points with convex-hull vertices has bounded triangular faces. Thus equal and equal ensure that the two triangulations have the same number of triangles, though this numerical agreement alone does not establish an isomorphism of their face lattices. Danciger, Devadoss, and Sheehy, Compatible Triangulations and Point Partitions by Series-Triangular Graphs
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.