CS6110: Computational Geometry Odd Semester, 2013
Instructor: John Augustine
Teaching Assistant: Prashanth Srikanthans
Class Meetings: Tuesdays 11 – 11:50, Wednesdays 10 – 10:50, Thursdays 8 – 8:50, and a tutorial hour on Fridays 2 – 2:50.
Pre-requisites: This course will benefit you best if you have taken CS2800 or CS5800 and done well.
Grading: Assignments (10×2=20), Quizzes (2×25=50), Presentation (10 + 20 = 30).
Computational Geometry: Algorithms and Applications, Third Edition, by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Springer-Verlag.
Geometric approxiomation algorithms, by Sariel Har-Peled. AMS. (Copy of early edition available for free.)
Randomized Algorithms, by Motwani and Raghavan.
Lecture Notes by David Mount.
Lecture Notes by Suresh Venkatasubramanian.
There is geometry all around us and, quite naturally, several geometric computational questions beg for answers. Learning to answer such questions will be the heart of this course.
While in many cases, the geometry around is quite obvious, it is not always so. Here's a non-obvious example. Consider a database of employees in a firm consisting of their age and salary. We can represent each employee as a point (x,y) where x is their age and y is their salary. Notice that queries of the form "get employees with age <= 30 and salary > Rs. 60,000" can be framed geometrically. Unsurprisingly, several algorithmic problems can be posed on geometric structures. To solve these problems, we will need to combine geometric insights with algorithmic techniques.
Line Segments Intersection
Art Gallery Problems and Polygon Triangulation
Quadtrees and approximate nearest neighbour queries
Well separated pair decomposition
Homeworks: An important emphasis in these assignments is to practice good formal writing. Therefore, I expect you to submit assignments as hard copies typeset in latex. Assignments are due at the start of class on the due date.
(Due Aug 06) Problem 1.8 of de Berg et al. Note that I expect you to compute the convex hull of two convex polygons even if they overlap.
(Due Aug 27) You are assigned three problems for this assignment.
i. Problem number 1.4 in BCKO (no discussions allowed).
ii. Problem number 1.6 in BCKO (discussions OK, but writing should be your own).
iii. In Chan's algorithm, we our guess values increased in the following manner: 2^2^0, 2^2^1, 2^2^2, .... Consider the variation in which the guess values increase slightly faster as follows: 2^2^2^0, 2^2^2^1, 2^2^2^2, .... (Answer the following questions without discussing with anybody)
a. Does the faster increase in the guess values asymptotically (i) increase the running time, (ii) maintain the same running time, or (iii) decrease the running time.
b. Formally justify your answer to part (a).
(Due Aug 11) Problems 2.14 and 3.14 of BCKO.
(Due September 18) Problems 5.1 & 5.10 (a & b only).
(Due September 19 BEFORE class starts) Problems 6.4 and 6.8 of BCKO. Solutions will be discussed during class.