Implementation of Geometric Algorithms is quite exciting. Moreover, animation of them are a lot of fun. In this project, I implemented two important algorithms to solve three interesting geometrical problems that are defined in section 1. Although I did not give the solution for Voronoi Diagram problem, this can be done using the Quad Edge data structure. Note that Voronoi Diagram is the dual of Delaunay Triangulation. There exist same number of edges in both. To construct the Voronoi Diagram it is enough to find all the edges of all the Voronoi regions. To find the Voronoi region of a vertex, one needs to find the centers of all circles that passes through the three vertices of all triangles that includes the given vertex. Connecting the centers of these circles gives us the Voronoi region. Using the Quad Edge Data Structure, this can be done without any additional asymptotic time cost. Actually, extension of the program to draw the Voronoi Diagram is under consideration (after the final exams.)
Another extension to the program should be made to handle the degenerate cases. For large number of points (more than 100) degenerate cases occur quite frequently. Simulation of Simplicity [4] which perturbs the points consistently, seems to be the best method to deal with those cases.
Program and the source code is available on the web together with this document: http://www-courses.cs.uiuc.edu//delaunay/
Finally, I would like to acknowledge that this project is done for the fullfillment of quarter credit of CS373 class that I have taken in Spring 97. I would like to thank Professor Herbert Edelsbrunner and his teaching assistants for this excellent class.