(Michel Pocchiola, Frédéric Chazal)
The main objective of the course is to give the students the fundamental knowledge to tackle the literature in computational geometry.
- Background and complementary material in topology. (3h, M. Pocchiola)
- Chirotopes, line arrangements, hyperplane arrangements, oriented matroids. (6h, M. Pocchiola)
- Geometric hypergraphs, Vapnik-Chervonenkis dimension, cuttings and epsilon-nets, simplicial range searching. (6h, M. Pocchiola)
- Tools and methods for the estimation and approximation of the topology and the geometry of sampled shapes: sampling and distance functions, homotopy, medial axis approximation, notions of topological persistence. (Chazal, 9h)
- B.Aronov, S.Basu, J.Pach, and M.Sharir, editors. Discrete and Computational Geometry - The Goodman-Pollack Festschrift, volume25 of Algorithms and Combinatorics. Springer-Verlag, June 2003.
- M. deBerg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
- E.Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
- J.E. Goodman and J.O'Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press, 2nd Edition, 2004.
- Allen Hatcher. Algebraic Geometry . Cambridge University Press, 2002.
- J. Matousek. Lectures on Discrete Geometry. Number 212 in Grduate texts in Mathematics. Springer-Verlag, 2002.
- K.Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
- Advanced Course On Combinatorial and Computational Geometry : trends and topics for the future. Notes of Course (series of lectures delivered by János Pach and Micha Sharir). Alcalá de Henares, Setembre 2006. Centre de Recerca Matemŕtica, Bellaterra (Spain)