Towards Compatible Triangulations

O. Aichholzer, F. Aurenhammer, F. Hurtado, and H. Krasser

Abstract:

We state the following conjecture: any two planar $n$-point sets (that agree on the number of convex hull points) can be triangulated in a compatible manner, i.e., such that the resulting two planar graphs are isomorphic. The conjecture is proved true for point sets with at most three interior points. We further exhibit a class of point sets which can be triangulated compatibly with any other set (that satisfies the obvious size and hull restrictions). Finally, we prove that adding a small number of Steiner points (the number of interior points minus two) always allows for compatible triangulations.

Reference: O. Aichholzer, F. Aurenhammer, F. Hurtado, and H. Krasser. Towards compatible triangulations. In J. Wang, editor, Proc. $7^{th}$ Ann. Int'l. Computing and Combinatorics Conf. COCOON'01, Lecture Notes in Computer Science, volume 2108, pages 101-110, Guilin, China, 2001. Springer Verlag.