Hints for PS #3                    

Here is a breakdown of PS #3 into small steps:

First, build a static triangulation and choose your triangulation data structure. I recommend chosing one of the following two ways to do this:

1.

Roll your own

1a.

Implement Melkman's algorithm for convex hull.

1b.

Add to the algorithm the identification of triangulation edges.

1c.

Pick a data structure for triangulations, and make Melkman's algorithm compute it.

2.

Steal a data structure

2a.

Use the quad-edge structure of Leonidas J. Guibas and J. Stolfi, ``Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.'' ACM Trans. Graph., 4(2):74-123, April 1985. Or see Dan Litchinski's implementation in Graphics Gems IV.

2b.

Both of these articles discuss how to build the Delaunay triangulation in this structure.

Once you have a static triangulation, make it move. This involves three steps that have minor variations depending on whether you are doing the Delaunay triangulation or some sort of lazy triangulation (that repairs triangles only when they are squashed flat).

i.

For each triangle (or for each triangulation edge), calculate the time at which it will be destroyed, based on the current neighboring triangles. This involves finding roots of a polynomial of degree 2 or 4.

ii.

From the event times, choose the next event.

iii.

Perform the swap indicated by the next event, and update the data structure and list of events based on the new triangles that are now present.