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