September 13 to October 28: Theory and problems
with Professor Ferran Hurtado.
November 4 to December 20: Theory and problems
with Professor Julian Pfeifle.
The two exams and the marks of the delivered problems
will combine for the final qualification.
The first problem list is here.
Every student must hand to the professor a written solution of problem 7 or problem 8 (but not both)
no later than Friday October 11.
The second problem list is here.
There will an exam on Monday October 28
during class hours (extended), from 5 to 8.
The exam will include some short theoretical questions, as well as the solution of a problem that will be proposed in situ.
The list of theory questions includes:
-2D point sets convex hull computation: lower bound via reduction, incremental algorithm with previous sorting,
divide&conquer algorithm with and without sorting, Graham's scan, Jarvis'march.
-Convex hull of 2 convex polygons.
-Rotating calipers technique and applications.
-Bentley-Ottmann line sweep algorithm to find intersections of segments, and applications.
-Basic properties of Voronoi diagrams.
Notice that other topics in the lectures, like abstract data types, DCEL, and triangulations, are not
considered for the theory questions.
Reference books for the first part of the course
BKOS: de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf,
O.: Computational Geometry, Algorithms and Applications, Ed.
BY: Boissonnat, J.; Yvinec, M.: Algorithmic Geometry. Ed. Cambridge University Press, 1997.
Ed: Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Ed. Springer-Verlag, 1987.
OR1: O'Rourke, J.: Computational Geometry in C. Ed. Cambridge University Press, 1998.
PS: Preparata, F.P. i Shamos, M.I.: Computational Geometry. An Introduction. Ed. Springer-Verlag, 1985.
DH: Ding-Zhu Du, Hwang, Frank: Computing in Euclidean Geometry.
World Scientific, 1995.
Mu: Mulmuley, K.: Computational Geometry: an Introduction through Randomized Algorithms. Ed. Prentice Hall, 1993.
OR2: O'Rourke, J.: Art Gallery Theorems and Algorithms. Ed. Oxford University Press, 1987
Pa1: Pach, J. (Ed.), New Trends in Discrete and Computational Geometry. Ed. Springer, 1993.
Pa2: Pach, J. i Agarwal, P. K.: Combinatorial Geometry. Ed. J. Wiley & Sons, 1994.