Updated April 15, 2003
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)
--------------------------------------------------------------