Number of hours
- Lectures 18.0
- Projects -
- Tutorials -
- Internship -
- Laboratory works -
- Written tests -
ECTS
ECTS 3.0
Goal(s)
This course presents basic tools for solving efficiently geometric and topological problems. We describe general techniques for the design and analysis of geometric algorithms such as complexity analysis, robustness issues and randomization. We introduce spatial search data structures, triangulations, Delaunay triangulations and Voronoi diagrams. We illustrate the course with applications to motion planning, surface reconstruction and surface meshing.
Responsible(s)
Francis LAZARUS
Content(s)
- The Art Gallery Problem
- Planar Graph & Triangulations by sweep-plane
- Range Searching
- Point Location
- Delaunay Triangulations and Voronoi diagrams
- Randomization
- Arrangements
- The Classification of Surfaces
- Surface Reconstruction
- Visibility Graphs & shortest paths
- Minkowski sum
- Meshing surfaces & Lifting Delaunay triangulations
Basic courses on the design and analysis of algorithms and data structures
Test
La note finale sera calculée à l'aide la formule suivante :
note finale = 0,4 * note projet + 0,6 * note examen écrit
L'examen écrit aura une durée de 2h. Les documents autorisés seront les notes de cours plus un livre au maximum.
Le projet consistera en une présentation d'article par groupe de 2 ou 3 étudiants.
The exam is given in english only 
Calendar
The course exists in the following branches:
- Curriculum - Master 2 in Computer Science - Semester 9 (this course is given in english only
)
Additional Information
Course ID : WMM9MO32
Course language(s):
The course is attached to the following structures:
You can find this course among all other courses.
Bibliography
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Ge- ometry: Algorithms and Applications. Springer, 2008.
Herbert Edelsbrunner. Geometry and topology for mesh generation. Cambridge University Press, 2001.
Ketan Mulmuley. Computational geometry: An introduction through randomized algorithms. Pren- tice Hall, 1994.