FME-UPC, 2013-2014

(page under construction)

Some previsions
and announcements:
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

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.