# CAS CS 591: Computational Geometry

## Assignment Due: Dec. 6, 2004

#### Programming Project

• [Main] Implement the random incremental Delaunay triangulation algorithm. The input is a point set in two dimensions. The output is the Delaunay triangulation.

Incorporate in a graphics package (even Matlab is ok) to display the output.

• [Extra] Apply Ruppert's refinement to improve the triangulation generated in part 1 so that all radius-edge ratio is at least 2.

• [1.] Prove the following statement:
For any point sets P = { p1, p2, ..., pn}, let T = DT(P) be the Delaunay triangulation of P. For all i, let pn(i) be the nearest neighbor of pi. Then (pi,pn(i)) is an edge of T. That is, the nearest neighbor graph of P is contained in the Delaunay triangulation of P.

Using this statement, show that the nearest neighbor graph of P can be computed in O(n log n) time.

• [2.] Prove the following statement: For any point sets P = { p1, p2, ..., pn}, the Delaunay triangulation of P
• [a.] minimizes the radius of the largest circumcircle, and
• [b.] minimizes the radius of the largest enclosing circle
among all triangulations of P, where the enclosing circle of a triangle is the smallest circle that contains the triangle (Question: when is the circumcircle of a triangle not its enclosing circle?)

• [3.] Let S = {1,2,3,...,n}. Suppose you build a binary search tree of S by first uniformly randomly permuting S, then incrementally adding elements from S according this permutation into an initially empty tree. Use the backward analysis to show that your randomized process builds the binary search tree for S in expected O(nlog n) time.

• [4.] Suppose X = {1,2,...,n} is a set of n numbers. If we choose a random element x from X , it is not hard to show that x is a (1/4)-median with probability 1/2. Now suppose we choose a sample of S of k random elements from X and let s be the median of S , then what is the probability that s is a c-median of X , where 0 < c < 1/2. You can write a program to run an experiment first to set up your conjecture before you prove it.

Make your bound as simple as possible. Note for grading: this homework is graded into three dimensional scores (f,b,c) where each score is 0--5, 5 is highest, and
f: the formulation score, 5 for correct formulation.
b: for simplication and estimation.
c: for meaningful experiment.

• [5.] We will add no more than 3 new question in the the next two weeks. That will be all the homework for this term.