Due 2:40 pm, November 25, 2009
20% of final grade
Implement either two divide-and-conquer algorithms or two incremental insertion algorithms for constructing two-dimensional Delaunay triangulations, described by Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74–123, April 1985. Feel free to skip Section 3, but read the rest of the paper. See also this list of errors in the Guibas and Stolfi paper, and Paul Heckbert, Very Brief Note on Point Location in Triangulations, December 1994. (The problem Paul points out can't happen in a Delaunay triangulation, but it's a warning in case you're ever tempted to use the Guibas and Stolfi walking-search subroutine in a non-Delaunay triangulation.)
Your implementations must use Guibas and Stolfi's quad-edge data structure (with appropriate simplifications, if you wish). You are responsible for reading and understanding the Guibas and Stolfi paper, except Section 3, which may be safely skipped. It's a long paper, so start early.
The purpose of this project is to burn an understanding of Delaunay triangulations and planar subdivision data structures into your brain.
Which of the two options should you choose? Well, the divide-and-conquer algorithm is faster, and will satisfy you better if you're a speed junkie. The incremental algorithm is more flexible because it's incremental, and therefore can be used in an on-line manner by mesh generators and other algorithms that choose vertices based on the state of the triangulation. I think the difficulty of the two implementations is equal. (Guibas and Stolfi's divide-and-conquer pseudocode is substantially more complicated than their incremental pseudocode, but the extra stuff you must devise yourself is more complicated for the incremental algorithm than for the divide-and-conquer algorithm.)
Next, implement a second version of the divide-and-conquer algorithm whose recursion alternates between using horizontal cuts (at even depths of the recursion tree) and vertical cuts (at odd depths) to divide the points into two subsets. In other words, you bisect the entire set of points by x-coordinate, then bisect each half-set by y-coordinate, then bisect each quarter-set by x-coordinate, and so on, alternating between directions. (This alternation is motivated by a paper by Rex Dwyer.) The original algorithm of Lee and Schachter (discussed by Guibas and Stolfi) uses vertical cuts only.
To bisect the sets quickly, I suggest using the standard O(n)-time quickselect median-finding/partitioning algorithm. It's not a good idea to fully sort the points at every level of the recursion, because if you do, you'll have a Θ(n log^{2} n) Delaunay triangulation algorithm, which defeats the speed advantage of alternating cuts.
You should find that you can use the same code to merge hulls regardless of whether the cuts are vertical or horizontal, but before/after you merge, you'll need to readjust the positions of the convex hull ``handles'' called ldi, rdi, ldo, and rdo in the Guibas-Stolfi paper.
Next, implement fast point location, based on either conflict lists or a history dag (whichever you prefer). Since you are using an edge-based data structure, rather than a triangle-based data structure, you will need to modify the point location data structure slightly.
Each quad-edge has four Data fields. Two of these are used to reference the vertices of the quad-edge. For point location based on conflict lists, the other two Data fields may be used to reference the lists of uninserted vertices associated with the triangles on each side of the edge. For point location based on a history dag, the other two Data fields may be used to reference the leaves of the dag associated with the triangles on each side of the edge.
For conflict lists, each uninserted vertex should maintain a reference to an oriented edge of the triangle that contains the uninserted vertex. For a history dag, each leaf of the dag should maintain a reference to an oriented edge of the triangle that the leaf represents.
An advantage of using these file formats is that I provide test data.
You should provide command-line switches, an input prompt, or some other easy way to choose among the options. For the divide-and-conquer algorithm, these options are alternating cuts versus vertical cuts only. For the incrmental algorithm, the options should include slow ``walking point location'' versus fast point location; and randomized insertion versus non-randomized insertion. Randomized insertion should select a permutation uniformly from all possible permutations. Non-randomized insertion should insert vertices in the order in which they appear in the input.
You should also submit a report (on paper) that includes the following: