Computational Geometry (CS504)

Spring Semester 2006

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!


Otfried Cheong. Office: E3-1 3434, Phone: 3542.

Teaching assistant

Mira Lee.


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.

Grading policy


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.

Tentative syllabus

The 16 weeks of the semester may be filled roughly like this:

  1. Introduction
  2. Line Segment Intersection
  3. Polygon Triangulation
  4. Linear Programming
  5. Orthogonal Range Searching
  6. Point Location
  7. Voronoi Diagrams
  8. Midterm exam
  9. Arrangements
  10. Interval & Segment Trees
  11. Convex Hulls
  12. Delaunay Triangulations
  13. Robot motion planning
  14. Mesh Generation
  15. Simplex Range Searching

Course progress

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

Midterm exam

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:

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:

Bulletin board

Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong