Topics in Computation Theory: Geometric Approximation Algorithms (CS700)

Spring Semester 2007

The first half of this course, before the midterm week, will be organized as a seminar course. We will discuss some fundamental, but slightly advanced, topics in computational geometry. Students give presentations.

The second half of the course will consist of a series of lectures given by Sariel Har-Peled on approximation algorithms in computational geometry. There will be homeworks, and perhaps a quiz.


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


CS500 Algorithms and CS504 Computational Geometry. For exemptions talk to the instructor.


The class meets Monday, Wednesday, and Friday from 11:00 to 11:50 in classroom 5 (room 3444) in the EECS building (E3-1). Presentations and lectures are given in English.

Grading policy

Students will be graded based on their presentation and homeworks. There may be a quiz. There will not be an exam.

Seminar presentations

We will cover several chapters and sections of the book Computational Geometry by de Berg et al., and some other papers:


We plan to cover techniques used in developing efficient approximation algorithms in computational geometry and related fields, such as:

Class notes for the lectures are available here.

Presentation schedule

02-26 Introduction Otfried
03-05 Smallest enclosing disks Samuel
03-07 On the beach Mira
03-09 A Framework for Randomized Incremental Algorithms Hasan
No seminar from 03-12 to 03-16 (Dagstuhl)
03-21 Convex hulls in 3D Janghwan
03-23 BSP-Trees in 3D Hyo-Sil
03-26 The space of spheres Jeong-Hyeon
03-28 The Dobkin-Kirkpatrick hierarchy I Chun-Seok
04-02 The Dobkin-Kirkpatrick hierarchy II Chun-Seok
04-04 Chan's technique Youngjun
04-06 Embeddings of Moving Points in Euclidean Space Sariel
04-09 Davenport-Schinzel sequences I Jung Gun
04-11 Davenport-Schinzel sequences I Jung Gun
No seminar from 04-16 to 04-20 (midterm week)
04-23 Linear time closest pair Sariel
04-25 Quad trees Sariel
04-30 WSPD Sariel
05-02 WSPD II Sariel
05-07 WSPD III Sariel
05-09 Brunn-Minkowski Sariel
05-14 Isoperimetric inequality Sariel
05-16 No class  
05-21 Measure concentration Sariel
05-23 JL Sariel
05-28 Ellipsoid I Sariel
05-30 Ellipsoid II Sariel
06-01 Querying Approximate Shortest Paths in Anisotropic Regions Antoine


The homework is available. The deadline is Friday, June 1st, 11am. Please bring it to the last class in the Oh Sang Soo seminar room.

Otfried Cheong