Discrete and Algorithmic Geometry - MAMME
FME-UPC, 2013-2014

(page under construction)

Some previsions and announcements:

September 13 to October 28: Theory and problems with Professor Ferran Hurtado.
Problem lists will be made available progressively. Students will have to hand some of the problems
to the professor (and possibly present the solution at the blackboard), when announced, and will
get marks for this.
There will be about 2 or 3 of these graded assignments.
There will also a be a short exam by the end of October, during class hours.

November 4 to December 20: Theory and problems with Professor Julian Pfeifle.
The students will take turns in taking notes during class and typing them up in LaTeX, thus expanding
the material and notes taken in previous years.
Problem lists will be made available progressively. Students will have to hand some of the problems
to the professor (and possibly present the solution at the blackboard), when announced, and will
get marks for this.
There will be about 2 or 3 of these graded assignments.
There will also a be a short exam by the end of December, during class hours.

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

Basic references

BKOS: de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O.: Computational Geometry, Algorithms and Applications, Ed. Springer-Verlag, 1997.
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.

Additional references

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.