Homework 4, Due Thursday, April 10, at the beginning of class

1) The Delaunay triangulation is but one example of a straight-line planar graph defined on a set P of n sites in the plane. Two others include the Gabriel graph and the relative neighborhood graph (or RNG). In both cases the vertices of the graph are the sites of P . In the Gabriel graph, two sites pi and pj are joined by an edge if the disk whose diameter is pipj contains no other sites. In the RNG, there is an edge joining pi and pj if there is no point pk in P that is simultaneously closer to pi and pj than they are to each other. That is, there is no pk such that:

max(dist(pi,pk),dist(pj,pk)) < dist(pi,pj)

(a) Find a set of (about 6 or 7) points for which the three graphs are all different. Draw the three graphs for these points.

(b) Prove that the Gabriel graph of P is a subgraph of the Delaunay triangulation of P.

(c) Prove that the RNG of P is a subgraph of the Delaunay triangulation of P .

2) In class we argued that the number of parabolic arcs along the beach line in Fortune's algorithm is at most 2n - 1. The goal of this problem is to prove this result in a somewhat more general setting.

Consider the beach line at some stage of the computation, and let

{p1,p2, ..., pn}
denote the sites that have been processed up to this point in time. Label each arc of the beach line with its the associated site. Reading the labels from left to right defines a string. (In the figure below the string would be:
p1p2p1p3p6p4p6p7p9

(a) Prove that for any i, j, the following alternating subsequence cannot appear anywhere within such a string:

...pi ... pj ... pi ... pj ...

(b) Prove that any string of n distinct symbols that does not contain any repeated symbols (... pipi ...) and does not contain the alternating sequence of the type given in part (a) cannot be of length greater than 2n - 1. (Hint: Use induction on n.)

3) Give an example of a point set (no four points cocircular) such that the minimum weight triangulation is not equal to the Delaunay triangulation. Explain your construction briefly. (Hint: four points suffice.)

<3.1>(extra credit). Question 3 says that the weight (sum of all the edge lengths) of the delaunay triangulation can be more than the minimum weight triangulation. How much more? If the weight of the delaunay triangulation is w(DT) and the minimum weight triangulation has weight w(MWT), what is the maximum value of: w(DT)/w(MWT)