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 p_i and p_j are joined by an edge if the disk whose diameter is p_ip_j contains no other sites. In the RNG, there is an edge joining p_i and p_j if there is no point p_k in P that is simultaneously closer to p_i and p_j than they are to each other. That is, there is no p_k such that:

max(dist(p_i,p_k),dist(p_j,p_k)) < dist(p_i,p_j)

(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. check out the middle of this page for a point set with 5 points.

(b) Prove that the Gabriel graph of P is a subgraph of the Delaunay triangulation of P. Let edge (a,b) be any edge of the gabriel graph. By definition of gabriel graph, the circle whose DIAMETER is the segment (a,b) has no other points inside it. By the "empty circle" property of delaunay triangulations (An edge exists between two points in the DT if ANY circle can be drawn through those two points and contain no other points), then edge (a,b) is in the DT. Therefore all edges in the gabriel graph are in the DT.

(c) Prove that the RNG of P is a subgraph of the Delaunay triangulation of P . Let edge (a,b) be any edge of the relative neighborhood graph (RNG). By definition of RNG, there is no point c in P that is simultaneously closer to a and b than they are to each other ---
so either dist(a,c) < dist(a,b) OR dist(b,c) < dist(a,b).
Now consider the circle drawn with the segment ab as the DIAMETER (the same circle we used in part a. consider a hypothetical point D inside that circle. No matter where D is, its distance to point A is smaller than dist(a,b), and its distance to point B is smaller than dist(a,b).

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

{p₁,p₂, ..., p_n} 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: p₁p₂p₁p₃p₆p₄p₆p₇p₉

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

...p_i ... p_j ... p_i ... p_j ... Recall that the arcs of the beach line are parabolic arcs. We claim that any two parabolas intersect in at most two points.
To see this, let y = P(x) and y = Q(x) be the equations for two parabolas. The x-coordinates of their common intersection will be at the roots of the equation P(x)-Q(x) = 0.
This is a quadratic equation in x, and hence it has at most two real roots. If such an alternation were to occur, then by the continuity of parabolas, between each pair of alternating arcs there must an intersection point. Three alternations would imply the existence of three intersection points, a contradiction.

(b) Prove that any string of n distinct symbols that does not contain any repeated symbols (... p_ip_i ...) 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.) Let L(n) denote the maximum length of a sequence of n distinct characters that satisfy our constraints. We prove that L(n ) 2n - 1 by induction on n. This is easily veried for n = 1.
Assume the hypothesis holds for any number of distinct symbols strictly less than n. Consider the first and last occurrences of the symbol A. They subdivide the string into three strings as shown below

wAuAv;
where w, u, and v are strings, and w and v contain no occurrences of an. Let wv be the con- catenation of w and v. Observe that if any symbol B (different then A) occurs in wv then it cannot occur in u, and vice versa, since otherwise we would have a forbidden alternation.
Thus, if k denotes the number of distinct characters in u then there are n-k distinct characters in wv. Clearly there can be no forbidden alternations in u nor in w. Also u cannot have any (immediately) repeated symbols. It is possible to have a single repeated symbol in w (where w1 and w2 come together) so, if we count this repeated character and the lengths of the strings u and w, the total number of symbols in the string is at most
L(n ) <= L(k) +L(n-k) + 1 < (2k - 1) + (2(n - k) - 1) + 1 <= 2n - 1;
completing the proof.
Strings with such forbidden alternations are called Davenport-Schinzel sequences, and they have a number of applications in computational geometry and other areas of combinatorics.

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.) Can I do this without drawing anything??? Draw a circle. Put four points on it. No no, not that way... put three points really close to one another, and one point all the way on the opposite side. let the close by points be a,b,c, (with b in the middle), and let d be the point on the far side of the circle. Have you actually drawn these points yet? If not, this wont make sense. Now, since we've put these points ON a circle, the DT isn't defined, because the points aren't in general position and all. Now nudge point a just barely outside the circle. the DT is triangle: b,c,d (because you have the circle (b,c,d) with no other point inside, + triangle a,b,d (because that is the only other possible triangle). the MWT is the triangle (a,b,c) [a nice, small triangle], and the triangle (a,c,d). This is clearly smaller weight, because you have only TWO edges that go all the way across the circle instead of 3 (which is what the DT uses).

<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)