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).

__Textbooks__:

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.)

__References__:

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.

__Lectures__:

Well separated pair decomposition

Johnson-Lindsenstrauss Lemma

VC-dimension

__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.