Computational geometry studies algorithms and data structures for processing and storing geometric objects. This courses discusses algorithm design techniques such as plane sweep and geometric divide & conquer; data structures such as point location structures, interval trees, segment trees, and BSP trees; and geometric structures such as arrangements, triangulations, Voronoi diagrams, and Delaunay triangulations.
Undergraduate students: I have deliberately asked for the course number to be changed from CS604 to CS504 so that undergraduate students can also attend this course. Computational Geometry is well suited for undergraduate students with an interest in algorithms. If you liked Algorithms (CS300), you'll probably also like Computational Geometry!
A graduate or undergraduate algorithms course (such as CS300 or CS500, or an undergraduate algorithms course you took before coming to KAIST).
The class meets Mondays and Wednesdays from 13:00 to 14:30 in classroom 4 (room 2245) in the EECS building (E3-1). Lectures are given in English.
We will be using the book Computational Geometry: Algorithms and Applications (second edition), by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Springer-Verlag 2004.
Another good reference for the course are David Mount's lecture notes.
The 16 weeks of the semester may be filled roughly like this:
The material covered in the lectures so far (Chapter 1 of the textbook is available on-line at the book website):
| 03-06 | Introduction, Planar convex hulls | 1.3, 1.2 (up to page 5) |
| 03-13 | Planar convex hulls, fixed-radius near neighbors | 1.2, David Mount's notes |
| 03-15 | Fixed-radius near neighbors, line segment intersection | pg. 20-22 |
| 03-20 | Line segment intersection | 2.1 |
| 03-22 | Planar maps, DCEL representation | 2.2 |
| 03-27 | Polygon triangulations | 3.1 |
| 03-29 | Triangulating a simple polygon | 3.2, 3.3 |
| 04-03 | Intersection of half-spaces, duality | 4.1, 4.2, 8.2 |
| 04-05 | Lower envelopes and upper convex hulls | 11.4 |
| 04-10 | Incremental linear programming | 4.3 |
| 04-12 | Randomized incremental LP | 4.4 |
| 04-17 | Randomized incremental LP | 4.4 |
| 04-19 | No class, midterm exam 19:00-22:00 | |
| 04-24 | No class (midterm week) | |
| 04-26 | Midterm review, Trapezoidal map | 6.1 |
| 05-01 | Cancelled (instructor was sick) | |
| 05-03 | Point location | 6.2 |
| 05-08 | Expected query time, degeneracies and symbolic perturbation | 6.2, 6.3 |
| 05-10 | Voronoi Diagrams | 7.1 |
| 05-12 | Delaunay triangulations | 9.1, 9.2 |
| 05-15 | Computing the Delaunay triangulation | 9.3 |
| 05-17 | Range trees, kd-trees | 5.1, 5.2, 5.3 |
| 05-22 | Interval trees, segment trees | 10.1, 10.3 |
| 05-24 | Minkowski sums | 13.3 |
| 05-29 | Minkowski sums and robot motion planning | 13.2, 13.4 |
| 05-31 | No class (election day) | |
| 06-05 | No class (conference) | |
| 06-07 | No class (conference) | |
| 06-12 | Project presentations | |
| 06-14 | Project presentations | |
The midterm exam will be held on April 19, from 19:00 to 22:00 in the evening, in our usual class room (classroom 4, room 2245). The exam will be open book - you can bring our text book and the notes you have taken in the course. No other books or printouts are allowed.
There will be a few (3 to 5) homework assignments in this course. You will have one or two weeks to complete an assignment. Homeworks can be turned in in English or Korean.
In the second half of the course, students will form teams of two or three students ("groups" of one student can be permitted with good reason, you need my approval), and select a topic for the final project. The project can be one of the following:
For all these problems solutions can be found in the literature or the internet. You are not supposed to search for such a solution, but to solve the problem yourself using the knowledge you've gained in the course (and reading the book).
The deadline for the project is June 12 at the beginning of the class. We will have presentations for all projects during the class hours on June 12 and June 14.
Project groups so far:
Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)