Algorithms
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 given in the previous section. 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 candidates stop.
- For each candidate diagonal D 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 one is, then Tk and Tj are realizable, and D is the generator. If not then continue with the next candidate.
If no generator has been found by this point, T1 and T2 are not realizable.
Inflation Algorithm:
By definition if a polygon P and its triangulations T1 and T2 are realizable then we should be able to find a convex polyhedron P* that is their realization. It turns out that for a given polygon if T1 and T2 are found to be realizable by the Realizability Algorithm described above, the algorithm used to inflate the triangulations is surprisingly simple:
- Run the Realizability Algorithm on T1 and T2. If T1 and T2 are realizable let D be the generator returned by the Realizability Algorithm. Otherwise abort the procedure since the hypothesis of Dekster's Theorem are not met.
-
For each vertex vi in P compute its orthogonal distance to the generating diagonal D, and assign this distance to the height of vi.
Correctness:
Both of these algorithms were extracted from the theorems, definitions, and diagrams contained in Dekster's paper. In private communication with Prof. Dekster he indicated that he was not aware of any prior algorithms based on his work in this area. The proof that these algorithms are correct rests entirely on the fact that Dekster's work (specifically Theorem 2) is correct. The proof of this theorem is contained in his paper, but it relies on a long and elaborate proof that I was unable to improve upon in any way so I simply refer the interested reader to see Dekster's paper for more information.
Implementation:
What is perhaps more convincing in this case then a full proof is a demonstration that these algorithms actually work. The Realizability Applet is a complete implementation of both of these algorithms, and allows the user to enter any polygon and pair of triangulations so they can see the results first hand.
|