On joint triangulations of two sets of points in the plane

Abstract

In this paper, we establish two necessary conditions for a joint triangulation of two sets of $n$ points in the plane and conjecture that they are sufficient. We show that these necessary conditions can be tested in $O(n^3)$ time. For the problem of a joint triangulation of two simple polygons of $n$ vertices, we propose an $O(n^3)$ time algorithm for constructing a joint triangulation using dynamic programming.

The extended abstrat of this paper appeared in the Proceedings of India-Taiwan Conference on Discrete Mathematics, Taipei, pp. 34-43, 2009