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.
| 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
|
