M. Tech. (CS) Second year, First semester, 2014

Course Outline | General Information | Study Material | Lectures (classwise) |

- Course Outline
The course consists of 2 double lectures per week.

The basic thrust of the course would be to study discrete and computational geometry.

We will try to stick to the basic course outline as given in

*this page*, but may deviate a bit.We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses and have some knowledge of elementary discrete probability.

- General Information:
Class Timings: Monday 14:15-16:05, Thursday 09:45-11:25

Room No. 709-710, S. N. Bose Bhavan (Library Building)The necessary evil - marks, exam, etc.: Mid-sem: 25, End-sem: 50, Internal evaluation: 25

- Study material:
Keep looking regularly for any updates
Books (B1) Computational Geometry: Algorithms and Applications

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars

Springer Verlag

(B2) Computational Geometry -- An Introduction

Franco Preparata and Michael Ian Shamos

Springer Verlag

(B3) Computational Geometry in C

Joseph O'Rourke

Cambridge University Press

(B4) Computational Geometry: An Introduction Through Randomized Algorithms

Ketan Mulmuley

Prentice Hall

(B5) Geometric Approximation Algorithms

Sariel Har-Peled

American Mathematical Society

(B6) Algorithms in Combinatorial Geometry

Herbert Edelsbrunner

Springer-Verlag

(B7) Algorithmic Geometry

J-D. Boissonnat and M. Yvinec

Cambridge University Press

(B8) Randomized Algorithms

Rajeev Motwani and Prabhakar Raghavan

CambridgeWeb Resources (W1) Lecture Notes by David Mount

(W2) Video lectures by Prof. Sandeep Sen - Lectures (classwise):
LECTURE DATES TOPICS NOTES (pdf) BOOKS Lecture 1

(04-08-2014)Introduction, convex hull in 2D -- lower bound,

Graham's scan, Jarvis march, output sensitive Chan's algorithm.- (B1), (B2), (W1) Lecture 2

(07-08-14)Range search -- Kd tree, Range tree - (B1), (B2), (W1) Lecture 3

(11-08-14)Range search (contd.) -- Fractional Cascading

Art Gallery theorem- (B1), (B2), (B3), (W1) Lecture 4

(12-08-14)Polygon triangulation: area of a simple polygon,

counting the number of triangulations in a convex polygon- (B1), (B2), (B3), (W1) Lecture 5

(14-08-14)Plane sweep -- the general paradigm

Line segment intersection- (B1), (W1) Lecture 6

(28-08-14)Doubly Connected Edge List (DCEL)

Triangulation of a monotone polygon- (B1), (W1) Lecture 7

(29-08-14)Voronoi diagram - (B1), (W1) Lecture 8

(04-09-14)Voronoi diagram - (B1), (W1) Lecture 9

(05-09-14)Duality - (B1), (W1) Lecture 10

(09-10-14)Duality - (B1), (W1) Lecture 11

(10-10-14)Duality;

Closest pair- (B1), (W1) Lecture 12

(22-10-14)Halfplane intersection;

Linear programming

(Randomized Incremental Construction)

Backward analysis- (B1), (W1)