Synthèse, image et géométrie

Synthèse, image et géométrie


Emploi du temps 2017-2018, séances de 3h de 13h à 16h
  • mardi 28 novembre [OD] (FTS-IECL-M09) Triangulation de Delaunay, intro, définitions et premières propriétés. Un algorithme O(n log n) dans le cas le pire.
  • mardi 5 décembre [OD] (FST-HP-E32) Simplifier les algorithmes sans trop perdre en rapidité: la randomisation. [+exercices]
  • mardi 9 janvier [OD] (FST-HP-E32) Un peu de complexité sous des hypothèses probabilistes. [+ mini-exam]
  • mardi 16 janvier [BL] () Reconstruction: comment retrouver une surface à partir de points de données
  • mardi 23 janvier [OD] (FST-HP-E32) Que faire quand les erreurs numériques sont géométriquement insensées ? [+ mini-exam]
  • mardi 6 février [BL] () Organiser des nuages de points - les arbres kd (kd-tree)
  • mardi 13 février [BL] () Échantillonage - algorithme de Lloyd [+mini-exam]
  • mardi 20 février [BL] () Re-maillage de surfaces [+mini-exam]
Contrôle des connaissances
  • un exam ecrit, organisé en 4 mini-sessions de 30mn les 9 et 23 janvier et 20 et 27 février de 16:30 à 17:00, documents autorisés, ordinateur interdit. (coeff 0.7, session septembre en cas de besoin).
  • un exposé (date sur rendez-vous avant début mars) pour présenter un article de recherche ou un mini-projet de programmation. (coeff 0.3, [dit controle continu] PAS DE session septembre pour le controle continu). Vous devez envoyer votre choix de sujet à Olivier Devillers ET Bruno Lévy, par courriel, avant le 13 décembre (un seul étudiant.e par sujet).
  • Liste des articles
    • L. P. Chew and S. Fortune. Sorting helps for Voronoi diagrams. Algorithmica, 18:217-228, 1997. link
    • Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. Journal of Computational Geometry, 2(1):30-45, 2011. link
    • Jeff Erickson. Dense point sets have sparse Delaunay triangulations or "...but not too nasty". Discrete & Computational Geometry, 33:83-115, 2005. link
    • Leonidas Guibas and David Marimont. Rounding arrangements dynamically. Internat. J. Comput. Geom. Appl., 8:157-176, 1998. link
    • J. Hershberger. Finding the upper envelope of n line segments in O(n log n) time. Inform. Process. Lett., 33:169-174, 1989. link
    • John Hershberger. Stable snap rounding. Computational Geometry, 46(4):403-416, 2013. link
    • David G. Kirkpatrick and Raimund Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287-299, 1986. link
    • R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):51-64, 1991. link
    • Jonathan Richard Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry, 18(3):305-363, October 1997. link
    • Arya, Mount, Netanyaou, An optimal algorithm for approximate nearest neighbor searching link
    • Du, Faber, Gunzburger, Centroidal Voronoi Tesselations: Applications and Algorithms link
    • Aurenhammer, Power diagrams: properties, algorithms and applications link
  • Projets développement: (langages au choix). Contacter B. Lévy pour plus de détails.
    • Projet 1: Implanter la méthode de paramétrisation de Tutte, qui permet de déplier en 2D un maillage 3D (homéomorphe à un disque). Je fournis quelques exemples de maillages.
    • Projet 2: Le robot "rubics cube" MindCuber en LEGO permet de résoudre le Rubics Cube. Il doit reconnaitre les couleurs des faces du cube. On se propose de développer un algorithme. Je fournis plusieurs jeux de données capteur du robot (à valider avec un algorithme existant pour résoudre le cube). Pour les étudiants très motivés je peux prêter un kit LEGO et les logiciels associés.
    • Projet 3: Structure de données Kd-tree: on se propose de développer l'algorithme des "K-means" qui permet de détecter les groupes (clusters) dans un nuage de point. Pour ceci il faudra développer une structure de données Kd-tree, afin de pouvoir appliquer l'algorithme a des grands nuages de données. Je fournis des points de données (issus de simulations de l'Institut d'Astrophysique de Paris).
Documents

Prérequis du cours

  • Il serait souhaitable de connaître un peu d'algorithmique. En particulier quelques algorithmes de tri (tri fusion, quick sort) et les arbres binaires équilibrés.

Contacter le responsable : Olivier.Devillers(at)inria.fr