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.

Lecturers:

Prerequisite:

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

Lectures

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:

• Section 4.7: Smallest Enclosing Discs.
• Section 6.4: A Tail Estimate.
• Section 7.2: Computing the Voronoi Diagram.
• Section 9.5: A Framework for Randomized Incremental Algorithms.
• Sections 11.1-11.3: Convex hulls in 3D.
• Section 12.4: The Size of BSP Trees in 3-Space.
• Chapter 16: Simplex Range Searching.
• Olivier Devillers, Stefan Meiser, and Monique Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. Research Report 1620, INRIA, Valbonne, France, 1992.
• David P. Dobkin and David G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. Journal of Algorithms 6(1985) 381-392.
  and
  David P. Dobkin and David G. Kirkpatrick. Determining the separation of preprocessed polyhedra: a unified approach In "Proceedings of the seventeenth international colloquium on Automata, languages and programming (ICALP)" 1990, pages 400-413.
• Timothy Chan. Geometric applications of a randomized optimization technique. Discrete & Computational Geometry 22(1999) 547-567.
• Pankaj K. Agarwal and Micha Sharir. Davenport-Schinzel sequences and their geometric applications.
• Pankaj K. Agarwal, Micha Sharir: Efficient Algorithms for Geometric Optimization. ACM Computing Surveys 30(1998) 412-458.
  There have to be at least two presentations based on this survey, on parametric search and on LP-Type problems. Another topic treated is the Frederickson-Johnson technique for searching based on a special kind of matrix.

Lectures

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

• Random sampling: epsilon-net and approximations.
• Discrepancy.
• Embeddings, dimension reduction, JL lemma, Bourgain's embeddings.
• Convex shape approximation - John theorem and Dudley theorem.
• Coresets.
• Shape fitting in low dimensions (with or without outliers).
• Fast clustering in low dimensions: k-center, k-median and k-means.

Presentation schedule

Homework

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.