IIT Kharagpur

Department of Computer Science and Engineering

Computational Geometry (Spring 2003) Course numbers PG 17638 and UG CS40010 (3-0-0) 3 Credits

Updated April 15, 2003

Class Test of 2 hours on Tuesday at 3:30 pm, February 18, 2003.

Quiz/Small test of 1 hour on Friday at 8:30 am, April 18, 2003.

------------ Books and References:

F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, New York, NY, Springer-Verlag, 1985.

Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag

Data Structures and Algorithms: Volumes I and III by Kurt Mehlhorn, Springer-Verlag.

Ketan Mulmuley, Computational Geometry: An Introduction through Randomized Algorithms.

Motwani and Raghavan, Randomized Algorithms.

K. Mehlhorn and S. Naher, LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge, UK, Cambridge University Press, 1999.

Considerable stress will be given on class tests and home assignments. Knowledge of elementary data structuring and progamming is required to register for this course. A prerequisite is Design and Analysis of Algorithms or its equivalent. The syllabus for this course is available in the department and in the UP and PG course brochures. Although the course has a PG number, all UG and PG students with proper prerequisites can credit this course.


Lectures Tuesdays 4:30 pm - 5:25 pm, Wednesdays 10:30 am - 11:25 am and Fridays 8:30 am to 9:25 am (last week of the course).


Topics covered (to be covered) in reverse order:

Finger searching with applications;

planar point location, Kirkpatrick's method, method using fractional cascading;

Helly's theorem-- applications for line transversals, arcs on a circle, covering a set of points, bounding the radius of a disc covering a set of points, proofs of Helly's and Radon's theorems;

arrangement of lines in the plane: bounds on the numbers of edges, vertices and faces, the zone theorem, constructing the arrangement and data structures for it, topological sweep of arrangements, computing smallest empty triangles for a point set;

plane sweep paradigm for computing triangulations of polygons and segments' intersections;

use of concatenable queues for computing convex hulls using divide and conquer, computing convex layers of a point set;

convex hull computation--incremental and prune-and-search algorithms;

computing Delaynay triangulations and Voronoi diagrams of point sets, the flip algorithm and its correctness;

lower bound proofs for problems of computing triangulations, convex hulls and closest pairs of points;


First assignment: Submission deadline in hardcopy handwritten sheets. February 3, 2003, AN.

Write clear and lucid designs and analyses leading to the methods as required in the following problems. Avoid and delay the use of pseudo-code and programs as much as possible in your solutions. Prove the correctness of various steps and claims as you carry out your design and analysis.

(1) Show that the area of the smallest convex region of the plane containing a given set of n points is computatble in O(n log n) time. (5 marks)

(2) Show how you can sort a set of n rationals using a convex hull algorithm. (10 marks)

(3) Show that Jarvis's march for computing the convex hull of n points in the plane requires time proportional to the number of edges of the final convex hull. (10 marks)

(4) Show that n rationals can also be sorted using an algorithm for traingulating a set of n points in the plane. (10 marks)

(5) Show how to compute a triangulation of a set of n points in the plane in O(n log n) time. (10 marks)

(6) Show that the union of two intersecting convex polygons can have O(n+m) edges where the two given convex polygons are of m and n edges each. (5 marks)

(7) Show that the convex hull of the union and the symmetric set difference of two overlapping convex polygons can be computed in linear time. (5 marks)

(8) Show that the convex hull of n points can be computed in linear time if they are sorted by their x-coordinates. (10 marks)

(9) Show that the convex hull of n points in the plane can be computed in O(n log h) time where h is the number of edges of the convex hull computed. (Hint: Let us find the upper and lower hulls separately. Find the edge e of the upper hull that intersects a vertical line dividing the given set of points in to two nearly equal halves. Suppose you can do this in less than cn time where c is a constant and n is the number of points given. What remains now is to find upper hull edges on the left and right halves of the edge e, recursively, and stop when all h1 edges of the upper hull are found. If h2 edges are in the lower hull, and h=h1+h2, then show that O(n log h) time suffices.) (15 marks)

(10) Consider height-balanced binary search trees permitting logarithmic cost insertions, deletions and search operations (logarithmic in the total number of nodes in the tree). Show that in such trees it is always possible to maintain a pointer from the root of each subtree to its extreme right leaf node, in all operations such as insertions, deletions and maintenance rotations for preserving the height-balanced nature of the tree. When we are at some subtree's root node say r, we can inspect the left child l of r, check l's extreme right leaf descendant and make a decision. A decision here could mean skipping the entire subtree rooted at l and only considering the right subtree of r for further work, or, vice versa i.e., dropping the right subtree of r and going down only the subtree rooted at l. Such a process can take at most logarithmic steps, logarithmic in the number of nodes in the tree and linear in the height of the height-balanced tree. Suppose we have two such height-balanced trees A and B of arbitrary heights. Assume that all keys in A are smaller than all keys in B. We wish to splice A and B into one height-balanced tree C. Show how this could be done in logarithmic time. On the other hand, we also need to be able to do a split, cutting such a tree C into two trees A and B at an arbitrary leaf of C, so that A and B are again height-balanced tree. Show how we could do this in logarithmic time. Could we do all these for also 2-3 and 2-4 trees? (20 marks)


Second Assignment. Submission by Feb 10, 2003.

Each question carries 20 marks.

(1) Construct examples of point set triangulations that are CYCLIC.

(2) Show that given 4 or more points in the plane, we can partition the set of points into two sets so that the convex hulls of the two sets overlap.

(3) Show that the any triangulation of a simple polygon has n-2 triangles.

(4) Show that any triangulation of a point set in the plane has less than 2n-4 triangles.

(5) A set S of n points is given in the plane so that no three points in S are collinear and no four in S are cocircular. Show that the Voronoi edge shared by Voronoi regions V_p and V_q (for two points p and q) is the locus of the centres of circles passing through p and q and not containing any other point of the set S.


Third Assignment. Submission by March 2, 2003.

(1) Generalize the problem number (2) of assignment two to d dimensions. (We did a proof in class on March 12, 2003; this is called Radon's Theorem.)

(2) Show how concatenable queues can be used to compute the convex layers of a point set in O(n log n log n) time.

(3) Show that there is always a centerpoint for a two dimensional point set S of n points. A point q in the plane is called a centerpoint of the set S if every half-plane not containing q has at most (2/3)n points of S. (Use Helly's theorem.)

(4) Show how you can compute the convex hull of a two dimensional point set of n points in O(log n) time with O(n) processors in the CREW PRAM model of parallel computation.

(5) Show that O(n log n) time is sufficient to detect whether there is any intersection at all within a set of n line segmenst in the plane. Is this bound tight? Why?

(6) Show that if every triple of a given set of n points in the plane can be covered by some unit disk then the whole set the n points can also be covered with some unit disc. Show that such checking for each pair of points will not ensure coverage of all n points by some unit disc. (Use Helly's theorem.)

(7) Give an O(n log n) algorithm for computing the diameter of a point set of n points in the plane. Is this upper bound tight? Why?

(8) Show that the diameter of a simple polygon can be computed in linear time.

(9) Suppose we have a convex quadrilateral abcd in the plane whose sides are ab, bc, cd and da in clockwise order and whose diagonals are ac and bd. Show that the circumcircle of triangle abc contains d if and only if the circumcircle of triangle cda contains b. Further show that if the circumcircle of triangle abc does not contain d then the circumcircle of triangle bcd must contain a.


Fourth Assignment. Submissions by March 15, 2003.

(1) Show that it is possible to triangulate some point set in the plane where some edge e of the triangulation may have "local Delaunay" property but e may not be an edge of the Delaunay triangulation of the given point set.

(2) Show that it is possible to find a Voronoi vertex of a point set S in the plane in O(n log n) time. Show that it is also possible to find a whole Voronoi region in O(n log n) time. Is a Voronoi vertex or a region computable in linear time?

(3) Is it possible to compute the Voronoi diagram or the Delaynay triangulation of a convex polygon in o(n log n) time? Linear time?


Study, thought and practice exercises, dated February 28, 2003:

(i) Triangulation of monotone polygons in linear time.

(ii) Computing the intersection of n half-planes.

(iii) Computing the kernel of a simple polygon. The kernel K is the set of points p inside a simple polygon from where each point q of the simple polygon is visible. Is the kernel a convex set? Why? Can you compute the kernel in linear time? How?

(iv) Computing the convex hull of a simple polygon.

(v) Computing the union and intersection of two convex polygons in linear time.

(vi) Development of a proof of Helly's theorem using induction on the number n of sets as well as the dimension d. (Helly's theorem is as follows: Given a collection S of n>d+1 compact and convex sets in R^d, the entire collection of n sets has a non-empty common intersection if each (d+1)-subset of the collection S has a non-empty intersection.)


Fifth assignment, March 11, 2003, submissions by March 23, 2003.:

(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, and

T(n,h)=c*n if h=2, where c is a constant,

has solution T(n,h)<= c*n*log h.

(vii) You are given n line segments in the plane. Show that the time complexity of determining whether there is at all any intersection between the segments is O(n log n). Is this bound asymptotically tight? Why?

(viii) Show that all s intersections between n line segments can be computed in O( (n log n) + s) time if each segment is either parallel to the x-axis or parallel to the y-axis. Can this bound be further improved? Why?


Grades scored:

Ex- Siddhartha Brahma (2nd year), Ruchi Malhotra (4th year), Vamsi Krishna (2nd year)

A- Gathala Sudha Anil Kumar (4nd year B Tech), A N Ramanathan (2nd year B Tech), V Srinivas Nori (2nd year B Tech), Hironmay Basu (4th year B Tech), J Suneeth Kumar (3rd year B Tech)

B- T Shashank Reddy (2nd year B Tech), V L Subrahmanyam (2nd year B Tech), Biplab Kisku (3rd year B Tech)

C- K B R Kashyap (2nd year B Tech)