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:

References:

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:

  1. Convex Hull

  2. Line Segments Intersection

  3. Art Gallery Problems and Polygon Triangulation

  4. Range Searching

  5. Point Location

  6. Voronoi Diagrams

  7. Delaunay triangulation

  8. Grids

  9. Quadtrees and approximate nearest neighbour queries

  10. Well separated pair decomposition

  11. Johnson-Lindsenstrauss Lemma

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

  1. (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.

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



  1. (Due Aug 11) Problems 2.14 and 3.14 of BCKO.

  2. (Due September 18) Problems 5.1 & 5.10 (a & b only).

  3. (Due September 19 BEFORE class starts) Problems 6.4 and 6.8 of BCKO. Solutions will be discussed during class.