Introduction

In this project, I worked on four interesting Computational Geometry problems. Computational Geometry is the branch of Computer Science that studies algorithms for solving geometric problems. Most of the algorithms books devote an entire chapter on it (e.g. [2] and [13]). Computational Geometry has many applications in computer graphics, robotics, VLSI design, computer-aided design, statistics and geographic information systems. Usually, the input to a computational geometry problem is a description of a set of geometric objects, such as a set of points, a set of line segments, a set of rectangles, etc. The output is often a response to a query about the given objects, such as any of the the lines intersect, or perhaps a new geometric object, such as convex hull of the set of points. Books on Computational geometry include those by Preparata and Shamos [12], Edelsbrunner [3], Lazslo [9], Mulmuley [10], and O'Rourke [11].

Let's first define the four problems that are related to this project. Note that following problems are all defined in two-dimensional space (plane). It is possible to extend them to higher dimensions. However, I implemented the algorithms that solves the problems in plane.

• 1. Convex Hull: Given a set S of n points in the plane, find its convex hull. The convex hull of a set is the smallest convex set that contains the set.

• 2. Triangulation : Given a set S of n points in the plane, construct a planar graph on the set of points such that each face within their convex hull is a triangle.

• 3. Delaunay Triangulation: Given a set S of n points in the plane find the Delaunay Triangulation. Delaunay Triangulation is a special triangulation which maximizes the minimum angle over all triangulations of the given set of points.

• 4. Voronoi Diagram : Given a set S of n points in the plane, construct the Voronoi diagram. Voronoi diagram partitions the plane into n equivalence classes, each of which corresponds to a point. Specifically, the equivalence class corresponding to is the Voronoi polygon which can be defined as the intersection of the half planes where is the half plane determined by the perpendicular bisector of the line and containing .

These problems has many applications in computer science. For example convex hull problem has applications in pattern recognition and image processing. Applications of Delaunay Triangulation include minimum spanning tree, nearest neighbour graph and finite element and interpolation methods as discussed in [5]. Voronoi diagram arise in nature in many situations. As discussed in [1], many computational problems, such as associative file searching, cluster analysis, scheduling record accesses and collision detection, are solved using Voronoi diagrams. Although the construction of the Voronoi diagram is not implemented in the content of this project, I want to state it as the fourth problem because of its close relation to Delaunay Triangulation. Voronoi diagrams are topologically equal to Delaunay Triangulations. In other words one is the dual of the other. For a detailed discussion of Voronoi diagrams and Delaunay Triangulations see [1], [5], [6] and [7].

In this project, algorithms to solve the first three problems are implemented. First two problems are solved simultaneously using the Plane Sweep algorithm. Third problem is solved using Edge Flip algorithm which takes the solution of second problem as the input. These algorithms are further discussed in section 2. Special data structures that are used by the algorithms are discussed in section 3. Non degeneracy assumption is made as discussed in section 4. The implementation animates the algorithms and gives statistics about the execution time and size of the output as further discussed in section 4. The analysis of the algorithms are given in section 5.