Implement **one** of the following algorithms:

What your clasmates are implementing

Feel free to work in groups of two, although I will expect a better job from a group of two. Also feel free to come and discuss the algorithms with me. I've described each of these algorithms in class and have also made papers available that describe the algorithms in more detail. Two of the papers are available on the web, and the third is in a JACM issue that is available the CS reading room (Soda 681).

**Note: Source code for some of these algorithms is
available on the web. If you choose to do a problem, please
do not look at anyone elses source until you
have handed in your implementation.**
You should feel free, however, to use other peoples code for
various subroutines such as implementing a heap.
Make sure you reference the code.

I have made some code for incremental Delaunay Triangulation available, which you might find useful for either of the first two algorithms. This is taken from the book "Graphics Gems IV", edited by Paul Heckbert, Academic Press, 1994. A copy of the associated chapter is available outside my door. The code is also available as part of a compressed tar file associated with the book. You might find, however, that it is just as easy if not easier to design your code from scratch since deciphering the code is not trivial. Also, as I mentioned in class, you might find a triangle based representation simpler (the code uses the quadedge representation). If you do use any part of the code, make sure to note in your code which parts you used.

You might also find Jonathan Shewchuk's Show-me code (showme.c) useful for plotting a set of triangles, or boundaries. It compiles for me using

```
````gcc -o showme showme.c -I/usr/sww/X11R6/include -L/usr/sww/X11R6/lib -lX11`

and for drawing triangles you can use .ele and .node
files.

Jim Rupert. ``A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation.'' Journal of Algorithms, 18(3):548-585, May 1995.

Michael Garland and Paul Heckbert. ``Fast Polygonal Approximation of Terrains and Height Fields.'' CMU-CS-95-181, CS Dept, Carnegie Mellon U., Sept. 1995.The algorithm I want you to implement is number III in the paper (the version I described in class).

**The test data files:** (Note: these are binary files in
STM format)

Paul B. Callahan and S. Rao Kosaraju. ``A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields.'' JACM, 42(1):67-90, January 1995

Available for copying in the CS reading room.

Points can be generated in the Kuzmin model by first generating
a random point *p* within a circle of radius 1. This can be done
by generating a random point within a square [-1,1],[-1,1] and
throwing the point out if it is not in the circle and trying
again.
Now scale the radius by

In particular

Repeat this process for each pont.

You can use a similar technique in 3 dimensions (by generating points in a unit cube). For the scaling, however, you should use

in 3 dimensions.

Back to the Algorithms in the Real World page.

Guy Blelloch, guyb@cs.berkeley.edu.