← All problems

Compatible Triangulations

25 years old · traced to

For an integer n≥3n\ge 3, let S1,S2⊂R2S_1,S_2\subset\mathbb R^2 be finite sets, each of size nn, with no three points collinear. Let hih_i be the number of vertices of the convex hull of SiS_i, and assume h1=h2h_1=h_2. A triangulation of SiS_i is a maximal noncrossing straight-line graph with vertex set SiS_i; its bounded faces are triangles. Is it always possible to choose triangulations T1,T2T_1,T_2 whose face lattices are isomorphic? Equivalently, is there a bijection ϕ:S1→S2\phi:S_1\to S_2 such that, for every three distinct points a,b,c∈S1a,b,c\in S_1, abcabc is a triangular face of T1T_1 if and only if ϕ(a)ϕ(b)ϕ(c)\phi(a)\phi(b)\phi(c) is a triangular face of T2T_2? 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 nn points with hh convex-hull vertices has 2n−2−h2n-2-h bounded triangular faces. Thus equal nn and equal hh 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

References

Progress summary

Never refreshed

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.