CSN-523: Computational Geometry (Spring 2014-2015)

M. Tech. (CSE) I Year and IDD (CSE) IV Year

Announcements:
- Demo Videos Published.
- Join Moodle site for assignment submission. Form group of two students. Deadline for submitting TS-1: Jan 27, 10:00 am.
- Venue for regular lecture classes has been changed to W-204.
- Students who have registered for this course, please join in Piazza.com class [Sign-up link: piazza.com/iitr.ac.in/spring2015/cs523].
Course Outline:
This is a course of Four (4) credit.

It consists of Three (3) lecture hours per week and One (1) hour tutorial.

The basic thrust of the course would be to familiarize the students with the design and analysis of efficient algorithms for geometric problems, typically in low dimensions (2,3,..). Its goal is to make students familiar with the important techniques and results in computational geometry, and to enable them to attack theoretical and practical problems in various application domains. These problems arise in a wide range of areas, including CAD, VLSI, robotics, computer graphics, molecular biology, GIS, spatial databases and sensor networks.

We will try to stick to the basic course outline as given in Syllabus, but may deviate a bit.

Prerequisite: CS-212 (Design and Analysis of Algorithms).

Evaluation Process (Marks, Examinations, etc.): Class Work Sessional (CWS) = 25%, Mid-Term Exam (MTE) = 25%, End-Term Exam (ETE) = 50%.

CWS will be computed from a weighted sum of different components.

General Information:

Elective Course for M.Tech. (CSE) I year, IDD IV year and PhD students: (Total Strength: 55)
Lecture Timings: Mondays (10 am - 11 am), Thursdays (11 am - 12 noon) and Fridays (11 am - 12 noon)
Lecture Venue: W-204
Course Instructor: Dr. Sudip Roy
Office time to meet the Course Instructor (for any kind of doubts): Monday - Friday (5:00 pm - 6:00 pm)
(To confirm the availability, please send an email before coming)
Teaching Assistants:

Gurram Prashanth (prashanth9929[at]gmail[dot]com)

Shashank Sheshar (shashank[dot]sheshar[at]gmail[dot]com)

Tushar Mehndiratta (mehnditm[at]gmail[dot]com)

Tutorial Timings: Tuesdays 3 pm - 4 pm (for MTech & PhD students), Wednesdays, 3 pm - 4 pm (for IDD students)
Tutorial Venue: S-308

Lectures (Class-wise):

Week	Lecture No.	Date	Day	Lecture Topic	Reference
1	1	5-Jan-2015	Monday	Introduction to Computational Geometry	[B1], [B2] [B3] [W1]
	2	8-Jan-2015	Thursday	Euclidean Geometry: Basic Definitions, Jordan's Curve Theorem, Simple Polygons, Jordan's Polygon Theorem, etc.
	3	9-Jan-2015	Friday	Planar Graphs, Polygons and Triangulation, Euler's formula
2	4	12-Jan-2015	Monday	PSLG vs simple polygon, Art Gallery Problem, Max-over-min formulation, Chvatal's conjecture	[B3]
	-	13-Jan-2015	Tuesday	Tutorial-1 for MTech & PhD	---
	-	14-Jan-2015	Wednesday	Tutorial-1 for IDD	---
	5	15-Jan-2015	Thursday	Art-Gallery Theorem, Triangulation Theory, Area of a Polygon, Point Inclusion of a Polygon, Implementation Issues	[B1]:Ch-3, [B3]:Ch-1
	6	16-Jan-2015	Friday	Triangulation Graph and Dual Graph, Fisk's Proof of Sufficiency, Monotone Polygons	[B1]:Ch-3, [B3]:Ch-1
3	7	19-Jan-2015	Monday	Polygon Partitioning into Monotone Polygons; Vertex Ontology; Plane Sweep Technique	[B1]:Ch-3, [B3]:Ch-2
	-	20-Jan-2015	Tuesday	Tutorial-2 for MTech & PhD	---
	-	21-Jan-2015	Wednesday	Tutorial-2 for IDD	---
	8	22-Jan-2015	Thursday	Polygon Partitioning into Monotone Polygons; Event Handling	[B1]:Ch-3
	9	23-Jan-2015	Friday	Triangulating a Monotone Polygon	[B1]:Ch-3, PDF file shared in Piazza
4	-	27-Jan-2015	Tuesday	Tutorial-2 for MTech & PhD	---
	-	28-Jan-2015	Wednesday	Tutorial-2 for IDD	---
	10	29-Jan-2015	Thursday	Triangulating a Monotone Polygon; Triangulating Simple Polygon: Diagonal-based Algorithm; Ear Removal Algorithm	[B3]:Ch-1, PDF file shared in Piazza
	11	30-Jan-2015	Friday	Partitioning Simple Polygon into Monotone Pieces: Plane-Sweep or Line-Sweep Algorithm; Triangulation of a Convex Polygon	[B1]:Ch-3
5	12	2-Feb-2015	Monday	Polygon Partitioning: Trapezoidalization of a simple polygon; Plane-sweep algorithm; Partitioning into Monotone Polygons after Trapezoidalization	[B3]:Ch-2
	-	3-Feb-2015	Tuesday	Tutorial-3 for MTech & PhD	---
	-	4-Feb-2015	Wednesday	Tutorial-3 for IDD	---
	13	5-Feb-2015	Thursday	Monotone Mountains; Partitioning into Monotone Mountains after Trapezoidalization; Triangulating a Monotone Mountain; Convex Partitioning; Constructing Simple Polygons	[B3]:Ch-2
	14	6-Feb-2015	Friday	Constructing Simple Polygons; Two measures of distance between two points:Euclidean and Manhattan; Data structure used in geometric algorithms: Doubly-Connected Edge Lists	[B1]:Ch-2
6	15	9-Feb-2015	Monday	Convexity and Convex Hulls; Two Naive Algorithms: Discarding non-extreme points, Keeping Extreme Edges	[B3]:Ch-3
	-	10-Feb-2015	Tuesday	Tutorial-3 for MTech & PhD	---
	-	11-Feb-2015	Wednesday	Tutorial-3 for IDD	---
	16	12-Feb-2015	Thursday	Hertel and Mehlhorn Algorithm for Convex Partitioning; Discussion on the tasks of CP-1	[B3]:Ch-2
	17	13-Feb-2015	Friday	Convex-Hull Problem: Gift-Wrapping (Jarvis's March) Algorithm; Quick-Hull Algorithm	[B3]:Ch-3, [B1]:Ch-1
7	18	16-Feb-2015	Monday	Convex-Hull Problem: Graham's Algorithm; Lower-Bound of Convex-Hull Problem	[B3]:Ch-3, [B1]:Ch-1
	-	17-Feb-2015	Tuesday	Tutorial-4 for MTech & PhD	---
	-	18-Feb-2015	Wednesday	Tutorial-4 for IDD	---
	19	19-Feb-2015	Thursday	Convex-Hull Problem: Incremental Algorithm; Divide and Conquer Algorithm (Preparata & Hong, 1977); Extension of these Two Algorithms for Convex-Hull Problem in Three Dimensions	[B3]:Ch-3
	-	20-Feb-2015	Friday	Class Postponed (Will be compensated after MTE)	---
8	20	23-Feb-2015	Monday	Convex-Hull Problem: Incremental Algorithm with sorting; Idea of Chan's Algorithm (1993); Triangulation of Point Set: Theory; Triangulating a Point Set: Incremental Algorithm without sorting and with sorting, Graham's Algorithm, Divide & Conquer Algorithm	[B3]:Ch-3
	-	24-Feb-2015	Tuesday	Tutorial-4 for MTech & PhD	---
	-	25-Feb-2015	Wednesday	Tutorial-4 for IDD	---
	21	26-Feb-2015	Thursday	Voronoi Diagrams: Definitions and Basic Concepts; Some Applications	[B1]:Ch-7, [B3]:Ch-5
	-	27-Feb-2015	Friday	Class Postponed (Will be compensated after MTE)	---
9	-	2-Mar-2015	Monday	Mid-Term Examination (1:45 pm - 3:30 pm) @ LHC-205	---
10	22	9-Mar-2015	Monday	Voronoi Diagrams: Definitions and Basic Concepts; Proof of Linear Complexity for Constructing Vor(P(n))	[B1]:Ch-7, [B3]:Ch-5
	-	10-Mar-2015	Tuesday	Demo of Coding Projects by MTech & PhD students	---
	-	11-Mar-2015	Wednesday	Demo of Coding Projects by IDD students	---
	23	12-Mar-2015	Thursday	Voronoi Diagrams: Basic Properties, Proximity and Empty Circles; Constructing Vor(P(n)): Intersection of Halfplanes; Point-Line Duality; Convex Hull and Halfplane Intersection	[B1]:Ch-7, [B1]:Ch-11, [B3]:Ch-5
	24	13-Mar-2015	Friday	Constructing Voronoi Diagrams: Incremental Algorithm, Divide-and-Conquer Algorithm	[B1]:Ch-7, [B3]:Ch-5
11	25	16-Mar-2015	Monday	Constructing Voronoi Diagrams: Fortune's Plane-Sweep Algorithm	[B1]:Ch-7, [W1]
	26	17-Mar-2015	Tuesday	Makeup Class (for 20-Feb-2015) Constructing Voronoi Diagrams: Fortune's Plane-Sweep Algorithm	[B1]:Ch-7, [W1]
	-	17-Mar-2015	Tuesday	Demo of Coding Projects by MTech & PhD students	---
	-	18-Mar-2015	Wednesday	Demo of Coding Projects by IDD students	---
	27	19-Mar-2015	Thursday	Some Minor Details of Fortune's Plane-Sweep Algorithm; Delaunay Triangulation: Basic Properties; Triangulation of a Point Set: Motivation of Delaunay Triangulation	[B1]:Ch-7 & Ch-9
	28	20-Mar-2015	Friday	Thale's Theorem, Angle Optimal Triangulation, Edge Flipping, Legal Triangulation Algorithm, Computing Delaunay Triangulation	[B1]:Ch-9
12	29	23-Mar-2015	Monday	Computing Delaunay Triangulation of a Point Set: Proof of Convergence of Edge-Flip Algorithm, Incremental Algorithm, Randomized Incremental Construction (RIC)	[B1]:Ch-9
	-	24-Mar-2015	Tuesday	Tutorial-5 for MTech & PhD	---
	-	25-Mar-2015	Wednesday	Tutorial-5 for IDD	---
	-	26-Mar-2015	Thursday	Class Postponed (Will be compensated later)	---
13	30	30-Mar-2015	Monday	Farthest-Point Voronoi Diagrams: It's Construction; Applications of Voronoi Diagrams and Delaunay Triangulation: Nearest Neighbor Query, Finding Closest Site, Max-Min Facility Location, Min-Max Facility Location, Constructing Euclidean Minimum Spanning Tree (EMST), etc.	[B1]:Ch-7, [B3]:Ch-5
	-	31-Mar-2015	Tuesday	Tutorial-6 for MTech & PhD	---
	-	1-Apr-2015	Wednesday	Tutorial-6 for IDD	---
14	31	6-Apr-2015	Monday	Application of Delaunay Triangulation: Constructing Euclidean Minimum Spanning Tree (EMST): O(nlogn) algorithm using Prim's or Kruskal's algorithms; 2-Approximation algorithm to solve Euclidean Traveling Salesman Problem (ETSP); Concept of Medial Axis and Straight Skeleton	[B3]:Ch-5
	32	7-Apr-2015	Tuesday	Makeup Class (for 27-Feb-2015) A short discussion on Art-Gallery Problem for External Visibility - Prison-Yard Problem; Intersection of Line-Segments: Bentley-Ottman's Sweep-line Algorithm	[B5]:Ch-6, PDF file shared in Piazza
	-	7-Apr-2015	Tuesday	Tutorial-6 for MTech & PhD	---
	-	8-Apr-2015	Wednesday	Tutorial-6 for IDD	---
	33	9-Apr-2015	Thursday	Arrangement of Lines: Combinatorics of Arrangements; Concepts of Zone & Levels; Zone Theorem; Computing DCEL of an Arrangement: Sweep-Line algorithm; Incremental Algorithm	[B1]:Ch-8, [B3]:Ch-6, PDF files shared in Piazza
	34	10-Apr-2015	Friday	Point-Line Duality: Primal and Dual Planes, Some Properties; Application of Arrangements: Ham-Sandwich Cut Problem, Ham-Sandwich Theorem; O(n+m) Algorithm for Solving 2D Ham-Sandwich Cut Problem; O(n^2) Algorithm for Testing whether Three Points are Collinear; Finding Minimum-Area Triangle in a Point Set	[B1]:Ch-8, [B3]:Ch-6, PDF files shared in Piazza
15	35	13-Apr-2015	Monday	Short Discussion on Geometric Data-Structures: Segment Tree and Interval Tree; Short Discussion on Intersection: Finding Intersection of Two Convex Polygons	[B1]:Ch-10, [B3]:Ch-7
	36	16-Apr-2015	Thursday	Short Discussion on Orthogonal Range Searching: 1-Dimensional Range Search, Kd-Trees	[B1]:Ch-5
	37	17-Apr-2015	Friday	Short Discussion on Robot Motion Planning Problem: Walking in a Triangulation; Configuration Space and C-Obstacles; Euclidean Shortest Path Problem: Elastic Band Concept; Finding Shortest Path in a Simple Polygon: Funnel Algorithm; Concept of Visibility Graph	[B1]:Ch-13.1, 13.2, Ch-15.1, [B3]:Ch-8.2, PDF files shared in Piazza
16	-	24-Apr-2015 - 1-May-2015	-	End-Term Examination (ETE)	---

Study Materials:

Books: (Let's see the Cover Pages)
- [B1] (Four Authors) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications (2nd Edition), Springer-Verlag.
- [B2] Franco P. Preparata and Michael Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag.
- [B3] (JOR) Joseph O'Rourke, Computational Geometry in C, Cambridge University Press.
- [B4] Subir Kumar Ghosh, Visibility Algorithms in the Plane, Cambridge University Press.
- [B5] Joseph O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987 (Available Online).
Web Resources:

[W1] Lecture notes by Prof. David Mount, Department of Computer Science, University of Maryland, USA
[W2] Website of Joseph O'Rourke: Homepage, Papers
[W3] CGAL: Computational Geometry Algorithms Library