Computational Geometry (Fall 2006)


The oral exams will take place Monday January 15, 2007 and Tuesday January 16, 2007. 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-024.


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.3, 7, 8.2, 9.1-9.3, 10 , 11.1-11.2, 12.1-12.3, 13-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. [BFJ02] Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, Cache-Oblivious Search Trees via Binary Trees of Small Height. Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 39-48, 2002. All
5. [ABFL05] Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, Morten Laustsen. Cache-Oblivious Planar Orthogonal Range Searching and Counting Proc. 21st Annual ACM Symposium on Computational Geometry, pages 160-169, 2005. All
6. [O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983. Chapter 7
7. [BV06] Henrik Blunck and Jan Vahrenhold. In-Place Algorithms for Computing (Layers of) Maxima. In: Lars Arge and Rusin Freivalds, editors: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), volume 4059 of Lecture Notes in Computer Science, pages 363-374. Springer, Berlin, 2006. © Springer-Verlag. All
8. [BV06b] Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope Selection. In: Tiziana Calamoneri, Irene Finocchi, and Giuseppe F. Italiano, editors: Proceedings of the 6th Conference on Algorithms and Complexity (CIAC 2006), volume 3998 of Lecture Notes in Computer Science, pages 30-41. Springer, Berlin, 2006. © Springer-Verlag. All
9. [BCC04] H. Brönnimann, T. M. Chan and E. Y. Chen, Towards in-place Geometric Algorithms and Data Structures. In Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG '04)', ACM Press, New York, NY, USA, pp. 239-246, 2004. All
10. [BIKMMT04] H. Brönnimann, J. Iacono,, J. Katajainen, P. Morin, J. Morrison and G. Toussaint, Space-efficient Planar Convex Hull Algorithms. Theoretical Computer Science 321(1), 25-40, 2004. All
11. [KMPSY04] Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Classroom Examples of Robustness Problems in Geometric Computations. In: Proc. of the 12th Annu. European Sympos. Algorithms (ESA'04), Bergen, Norway. LNCS 3221, Springer, pp. 702-713, September, 2004. All

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