(i) Consider a diagonal flip in a quadrilateral abcd 
in any triangulation T of a set S of n points
in the plane. Due to the flip inside the quadrilateral abcd 
of T, the locally non-Delaunay 
diagonal ac is replaced by bd, thereby changing the triangulation from T to T'.
Show that this results in a non-zero reduction in the power of every point x
inside abcd with respect to the circumcircle of the traingle containing x 
in the changing triangulation. Initially the triangulation is T and the 
flip causes it to become T' with the only difference that ac is replaced by bd.
What is the significance of this result?

(ii) Conisder red-black trees. Show that the total work  
required for all rebalancing steps is O(n) if there are n operations 
(insertions and deletions), starting 
from an empty tree. We ignore all searching costs.
What is the significance of this result?

(iii) Suppose we systematically perform diagonal 
flips for non-locally Delaunay edges, starting 
from any triangulation T of a set S of n points in the plane. 
Show that an edge once flipped and therefore removed from the 
current triangulation, will never reappear again after any future flip.

(iv) You are given a convex n-gon P. You are supposed to do linear time 
preprocessing, thereby creating some suitable data struture S so that 
the following query can be answered in O(log n) time: Given a line in the 
plane, determine whether it intersects C, using the data structure S. What 
preprocessing will you do and how will you use your proposed data structure
S to answer the query in O(log n) time.

 
(v) Show that the Delaunay triangulation of a set S of n points in the plane 
is unique. Show also that the Delaunay triangulation maximizes the minimum 
angle in the triangulation, over all possible triangulations of the 
point set S. 

(vi) Show that the recurrence
T(n,h)= max{T(n/2,h1)+T(n/2,h2)+c*n | h1+h2=h, h>2}
T(n,h)=c*n if h=2, where c is a constant 
has solution T(n,h)<= c*n*log h.