Realizability
Realizability:
As seen in the Guiba's Conjecture section, the tetrahedron pictuered here was produced by raising two of the polygon's verticies (B and D) out of the plane. We say that the two triangulations T1 and T2 of the quadralateral ABCD are realizable since we are able to create a convex polyhedron (the tetrahedron) whose convex hull projects back onto T1 and T2. Formally, we have the following:
|
|
Definition: A polygon along with two triangulations T1 and T2 is said to be realizable if each vertex in P can be assigned a height such that the edges of the
top of the convex hull of the spatial polygon P' poject onto T1, and the edges of the bottom
of the convex hull of the spatial polygon P' project onto T2.
In the case of the abve tetrahedron, the spatial polygon is defined by the edges AB, BC, CD, and DA shown in black. These edges are the only edges common to both the top and the bottom of the convex hull of the spatial polygon. The remaining edge of the bottom is AC shown in blue, while the remaining edge of the top is BD shown in red.
Realizability of Convex Quadralaterals:
It should be intitivly obvious that the diagonal triangulations of any convex quadralateral are realizable. Since the number of diagonals in a diagonalization of a convex polygon of n sides is always n-3, the diagonalization of a convex quadralateral has exactly one diagonal. Since a diagonal must connect two verticies that do not define an edge of the polygon, we have that a quadralateral has exactly two distinct diagonalizations, and thus two distinct diagonal triangulations T1 and T2. As in our example above, these diagonals have to cross in the plane. By assigning the same non-zero height to the pair of verticies connected by the diagonal T1, we prevent T1 and T2 from intersecting while creating the required convex polyhedron, a tetrahedron in each case.
Dekster's Realizability Theorem:
The realizability of convex quadralaterals is actually a special case of the realizability of a larger class of polygons and triangulations. This larger class of objects is captured by Dekster's Realizability Theorem, which gives a sufficent condition for realizibility. In order to describe this theorem we will first need a few more difinitions:
Definition: Given a polygon P, a diagonal D*=AB generates a triangulation T if and only if D* crosses all the diagonals in T in the order specified by the non-standard relation ≤R given below.
- (X1 < A) and (X1 ≤ X2 < A) then X1 ≤R X2.
- (X1 < A) and (X2 < X1 or B ≤ X2 or X2=w) then X2 ≤R X1.
- (X1 = w) and (X2 < A or X2=w) then X1 ≤R X2.
- (X1 = w) and (B ≤ X2 or X2=w) then X2 ≤R X1.
- (X1 > B) and (X2 > X1 or X2 < A or X2=w) then X1 ≤R X2.
- (X1 > B) and (B ≤ X2 < X1) then X2 ≤R X1.
where A and B are the end points of D*, w specifies the value of infinity, and Xi is the distance along the line AB where the line through an edge of P intersects the line through AB.
Theorem: Let P be a convex Polygon in general position. Let T1 and T2 be its triangulations. Suppose T2 is generated by a diagonal fron T1, or T1 is generated by a diagonal from T2, then T1 and T2 are realizable.
|
Example: Consider the octogon shown here at the right along with the specified diagonal D*=AB. If all the diagonals in T have to cross D* then they must all be of the form PiQj. Thus we know that the diagonal P1Q1 has to be an edge in T. If it isn't, then we won't be able to obtain a complete diagonalization of the octogon using diagonals that cross D*.
|
|
|
The next diagonal after P1Q1 along D* is either P1Q2 or P2Q1.We decide which one to pick by computing the intercepts Pi and Qi of the lines through P2P1 and Q2Q1 with the line through AB. If we think of the line through AB as a new x-axis with 0 at A, then define d(Pi) to be the distance of Pi from A along the new x-axis, and d(Qi) to be the distance of Qi from A along the new x-axis. If d(Qi) <R d(Pi) then the next diagonal we add is Q1P2. If d(Pi) <R d(Qi) then the next diagonal we add is Q2P1.
|
|
|
In our case d(Pi) is less than A and d(Qi) is less than d(Pi) so d(Qi) <R d(Pi) and the next diagonal is Q1P2. Continuing on in this way we can determine all the diagonals generated by D*.
|
|
Realizability Algorithm:
A general procedure for testing whether a polygon with two triangulations satisfies the hypotheses of Dekster's Realizability theorem can be extracted from the example above. The algorithm is as follows:
For k=1, j=2 and k=2, j=1:
- Check if there are diagonals in Tj that cross all the diagonals in Tk. Put each such diagonal in a list of candidates. If there are no candiadates Tk and Tj are not realizable.
- For each candidate in the list of candidates from Tj, determine the pair of triangulations it generates, and check if either of the generated triangulations is exactly equal to Tk. If it is, then Tk, and Tj are realizable. If not then continue with the next candidate.
- If there are no candidates left Tk and Tj are not realizable.
|