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.

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.

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

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.

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.

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