Les algorithmes géométriques sont une catégorie de méthodes informatiques utilisées pour résoudre des problèmes liés aux formes géométriques et à leurs propriétés. Ces algorithmes traitent des objets tels que les points, les lignes, les polygones et d'autres figures géométriques.

Dans de nombreux domaines de l'informatique tels que la robotique, l'infographie, la réalité virtuelle et les systèmes d'information géographique, il est nécessaire de stocker, d'analyser et de créer ou de manipuler des données spatiales. Ce cours traite des aspects algorithmiques de ces tâches : nous étudions les techniques et les concepts nécessaires à la conception et à l'analyse d'algorithmes géométriques et de structures de données. Chaque technique et concept sera illustré sur la base d'un problème survenant dans l'un des domaines d'application mentionnés ci-dessus. Objectifs : A la fin de ce cours, les participants devraient être capables - de décider quel algorithme ou structure de données utiliser pour résoudre un problème géométrique de base donné, - d'analyser de nouveaux problèmes et de trouver leurs propres solutions efficaces en utilisant les concepts et techniques du cours. Prérequis : Afin de suivre ce cours avec succès, vous devriez déjà avoir une connaissance de base des algorithmes et des mathématiques. Voici une courte liste de ce que vous êtes censé savoir : - O-notation, Ω-notation, Θ-notation ; comment analyser les algorithmes - Calcul de base : manipuler des sommations, résoudre des récurrences, travailler avec des logarithmes, etc. - Théorie des probabilités de base : événements, distributions de probabilités, variables aléatoires, valeurs attendues, etc. - Structures de données de base : listes chaînées, arbres de recherche binaires, etc. Terminologie des graphes - Compétences en programmation pour les travaux pratiques La majeure partie du contenu de ce cours est basée sur le livre suivant : M. de Berg, O. Cheong, M. van Kreveld, et M. Overmars. Computational Geometry : Algorithms and Applications (3e édition). Il n'est pas obligatoire d'acheter ce livre. Cependant, si les participants veulent en savoir plus que ce qui est proposé dans ce cours ou s'ils veulent revoir le matériel discuté dans les conférences, nous recommandons l'achat de ce livre. Les conférences vidéo contiennent quelques erreurs mineures. Vous trouverez une liste de ces erreurs dans la rubrique ressources. Si vous pensez avoir trouvé une erreur, signalez-la en cliquant sur le drapeau carré en bas du cours ou du quiz où vous avez trouvé l'erreur.