Compatible Triangulations and Point Partitions by Series Triangular Graphs

Computational Geometry: Theory and Applications 34, 195--202
2006

We introduce series-triangular graph embeddings and show how to partition
point sets with them. This result is then used to prove an upper bound on the number
of Steiner points needed to obtain compatible triangulations of point sets. The problem is
generalized to finding compatible triangulations for more than two point sets and we show
that such triangulations can be constructed with only a linear number of Steiner points added
to each point set. Moreover, the compatible triangulations constructed by these methods
are regular triangulations.

@article{danciger06compatible, Author = {Jeff Danciger and Satyan Devadoss and Donald R. Sheehy}, Journal = {Computational Geometry: Theory and Applications}, Pages = {195--202}, Title = {Compatible Triangulations and Point Partitions by Series Triangular Graphs}, Volume = {34}, Year = {2006}}