Computational Geometry (Fall 2004)


The oral exams will take place Monday January 10, 2005 and Tuesday January 11, 2005. The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the three projects and the material covered in class. The final grade will be based on the project reports and the oral examination. A grad will be given on the 13-scale.

The exam takes place in Turing-016.


1. [BKOS] Computational Geometry: Algorithms and Applications. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Second Edition. Springer-Verlag, 367 pages, 2000. ISBN: 3-540-65620-0. Chapters 1-3, 5, 6.1-6.2, 7, 8.2, 9.1-9.3, 10 , 11.1-11.2, 12-15, 16.1-16.3
2.[C96] Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996. Sections 1-2, 4
3. [ST86] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 1986, pages 669-679. All
4. [O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983. Chapter 7
5. [S98] Sven Skyum, Lecture note on Introduction to lower bounds, February 1998. Chapter 11
6. [A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003. Sections 1-2
7.[BGH99] Julien Basch, Leonidas J. Guibas and John Hershberger, Data Structures for Mobile Data, Journal of Algorithms, 31(1), 1999, pages 1-28. Sections 1, 4
8. [H04] Herman J. Haverkort, Introduction to bounding volume hierarchies, Manuscript, May 2004. All

This page is maintained by Gerth Stølting Brodal <>