Fundamental objects and techniques in computational geometry

(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)

Bibliography:

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