Compatible triangulations of point sets
Triangulations $T_1$ and $T_2$ of planar point sets $S_1$ and $S_2$ are compatible if their face lattices are isomorphic: there is a bijection $\phi\colon S_1 \to S_2$ such that $ijk$ is a triangle of $T_1$ empty of points of $S_1$ if and only if $\phi(i)\phi(j)\phi(k)$ is a triangle of $T_2$ empty of points of $S_2$.
Aichholzer, Aurenhammer, Hurtado and Krasser conjectured that the statement below holds, and proved it when at most three points lie inside the convex hull. Without general position the answer is sometimes no, and Saalfeld showed that compatible triangulations need not exist when the bijection is fixed in advance. Adding a linear number of Steiner points always suffices.
Problem. Prove or disprove that two planar point sets in general position always admit compatible triangulations when they have the same size $n$ and equally many points on their convex hulls.
Source: Aichholzer, Aurenhammer and Krasser (2001); Aichholzer, Aurenhammer, Hurtado and Krasser (2002); Problem 38 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- compatible triangulations, morphing, point sets, The Open Problems Project
References
@inproceedings{aichholzer2001,
author = {Aichholzer, Oswin and Aurenhammer, Franz and Krasser, Hannes},
title = {On Compatible Triangulations of Point Sets},
booktitle = {Abstracts 17th European Workshop Comput. Geom.},
publisher = {Freie Universit{\"a}t Berlin},
year = {2001},
pages = {23--26},
}
@article{aichholzer2002,
author = {Aichholzer, Oswin and Aurenhammer, Franz and Hurtado, Ferran and Krasser, Hannes},
title = {Towards compatible triangulations},
journal = {Theoret. Comput. Sci.},
volume = {296},
year = {2002},
pages = {3--13},
doi = {10.1016/S0304-3975(02)00428-0},
}
@inproceedings{saalfeld1987,
author = {Saalfeld, A.},
title = {Joint triangulations and triangulation maps},
booktitle = {Proc. 3rd Annu. ACM Sympos. Comput. Geom.},
year = {1987},
pages = {195--204},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01085, "Compatible triangulations of point sets", clopen.solutions.