Joint Triangulation of Two Point Sets in 2D

Subir Kumar Ghosh
School of Technology & Computer Science
Tata Institute of Fundamental Research, Mumbai 400005, India.
Ajit Arvind Diwan
Department of Computer Science and Engineering
Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.
Partha Pratim Goswami
Institute of Radiophysics and Electronics
University of Calcutta, Kolkata 700009, India.
Andrzej Lingas
Department of Computer Science
Lund University, S-221 00 Lund, Sweden.

Let A = {a₁, a₂, …, a_n} and B = {b₁, b₂, …, b_n} be two disjoint sets of points in the plane, specified by their respective x and y coordinates. Here the problem is to find triangulations of A and B (say, T(A) and T(B)) such that for each region bounded by a triangle a_ia_ja_k in T(A), the corresponding triangle b_ib_jb_k bounds a region in T(B). Following Figure shows an example.

The problem was posed in 1987 by Saalfeld and it has an application in automated cartography. Over the last two decades, several researchers have worked on this problem but the problem is still open. We have proposed two necessary conditions for the given point sets to satisfy if there exists a joint triangulation. But it is not known whether the necessary conditions are also sufficient.

A triangle a_ia_ja_k is said to be an empty triangle in A if it does not contain any point of A in its interior. Let S_A denote the set of all empty triangles in A whose corresponding triangles in B are empty triangles in B. Let S_B be the set of triangles corresponding to the triangles in S_A. It follows from the definition of a joint triangulation that only triangles from S_A and S_B can be component triangles in a joint triangulation of A and B.

Let a_ia_ja_k and a_ia_ja_l be two triangles in S_A lying on opposite sides of their common edge a_ia_j. If b_ib_jb_k and b_ib_jb_l also lie on opposite sides of their common edge b_ib_j, then a_ia_ja_l is a called a successor triangle of a_ia_ja_k on the edge a_ia_j and vice versa. Analogously, b_ib_jb_l is also called a successor triangle of b_ib_jb_k on the edge b_ib_j and vice versa. Intuitively, if a triangle ijk is a component triangle in a joint triangulation, one of the successors on each edge of ijk, that is not a convex hull edge, is also a component triangle in the joint triangulation. Let S denote the maximal subset of triangles in S_A and S_B such that each triangle ijk in S has at least one successor triangle in S, on the edges ij, jk and ki that are not convex hull edges. We call triangles in S as legal triangles and S is called the set of legal triangles.

The necessary conditions are now stated as follows.

1. If there exists a joint triangulation of A and B, then a_ia_j is an edge of the convex hull of A if and only if the corresponding edge b_ib_j is an edge of the convex hull of B.

2. If there exists a joint triangulation of A and B, then the set of legal triangles S is not empty.

Our conjecture is:

“There exists a joint triangulation of A and B if and only if A and B satisfy the two necessary conditions. ”

In support of our conjecture, we provide here a Java implementation of the two necessary conditions. Implementation has been done by Priya Banerjee and Puspita Roy, B. Tech(IT), Institute of Radiophysics and Electronics, University of Calcutta, Kolkata 700009, India.

The applet, on starting, presents two canvases where two sets of points can be generated. There is also a text box and a set of control buttons. Points can be generated in two ways. By inserting a number in the provided text box, one can click on the “GENERATE POINTS” button for generating given number of points randomly. Alternatively, one can click the “MANUAL POINT GENERATION” button and start creating points by pointing the mouse pointer at the appropriate position on any canvas and then clicking the left mouse button. Clicking of the right mouse button on an existing point will delete the point. In either mode, the two sets of points thus created are identical. After generating the points, one can change the position of any point by dragging it with the left mouse button. When the two sets of points are final, “STEP” button can be pressed to start computation. First time pressing of the “STEP” button computes the convex hulls of the two point sets and check if the first necessary condition is satisfied. Second time pressing generates the set S of all triangles. Third time pressing computes those triangles ijk from S which are empty in both the point sets and deletes all nonempty triangles. Fourth time pressing computes the successor triangles of each triangle ijk in S and checks if at least one successor of each edge is also in S. The triangles which do not pass this test are deleted from S. Finally, fifth time pressing of the “STEP” button creates a joint triangulation by taking triangles from S. At any point of time, the “RESET” button can be clicked to bring the applet at its starting position.

Let P_A and P_B be sets of points for which, after the fourth step, the set S is nonempty and still the fifth step can not produce a joint triangulation. Then P_A and P_B provide a counter example to our conjecture. One of the intentions of the present experimentation is to see if any such points can be generated.

To start the applet, click here.

For any comment or query please mail to Prof. Subir Kumar Ghosh.