INF562 -- Computational Geometry: from Theory to Applications (2010)

Luca Castelli Aleardi et Steve Oudot

présentation générale - supports de cours - programme des séances - organisation pratique du cours - propositions de stages - La géométrie algorithmique en France et dans le monde

Présentation générale

Computational geometry is a rather novel field whose aim is to study the properties of geometric objects such as point clouds, arrangements, geometric graphs or triangulations, both from a combinatorial and from an algorithmic point of view.

This course proposes a walkthrough of the discipline, to illustrate its variety in terms of topics as well as its potential in terms of applications. In this context, we will introduce a panel of theoretical questions, from very classical (e.g. computing convex hulls or Delaunay triangulations) to very recent (e.g. reconstruction from unorganized point clouds, approximation of geometric NP-complete problems, or effective proximity queries in high dimensions). Our goal will be twofold: on the one hand, to emphasize the elegance and theoretical soundness of the proposed approaches; on the other hand, to illustrate their practicality through a range of applications in computer graphics, robotics, machine learning, and image processing.

News

• 16/03/2010 : mise à jour du polycopié (section 1.3 et 6.3); la nouvelle version électronique remplace l'ancienne.
• 16/03/2010 : le sondage sur le cours INF562 est maintenant disponible.
• 03/03/2010 : mise à jour du polycopié (chap 5); la nouvelle version électronique remplace l'ancienne.
• 17/02/2010 : mise à jour du polycopié (sections 3.3.1, 3.4.1 et 3.4.3); la nouvelle version électronique remplace l'ancienne.
• 14/02/2010 : mise à jour du polycopié (section 4.1); la nouvelle version électronique remplace l'ancienne.
• 11/02/2010 : mise à jour des sujets de mini-projets.
  
• 31/01/2010 : les sujets de mini-projets sont maintenant disponibles. N'hesitez pas a y jeter un oeil et a venir en discuter avec nous mardi prochain !
• 25/01/2010 : mise à jour de la bibliothèque Jcg et de sa documentation. En particulier, les triangulations 3D ont été ajoutées.
• 06/01/2010 : mise à jour du polycopié (section 1.4.2 et définition 2.1); la nouvelle version électronique remplace l'ancienne.
• 04/01/2010 : le polycopié du cours est maintenant disponible au format pdf

Supports de cours

• Une petite introduction sur le cours (transparents au format pdf)
• Le syllabus au format html
• Le polycopié au format pdf
• La documentation de la bibliothèque Jcg
• La dernière version de la librairie Jcg (9 Mars 2010): Jcg.jar (sources).
• anciennes versions:
• 9 Mars 2010: Jcg.jar (sources)
  
• 25 Février 2010: Jcg.jar (sources)
  
• 16 Février 2010: Jcg.jar (sources)
  
• 26 Janvier 2010: Jcg.jar (sources)
  
• 19 janvier 2010: Jcg.jar (avec sources incluses)
  
• 12 janvier 2010: Jcg.jar
  
• 5 janvier 2010: Jcg.jar (sources)

Programme des séances

Slides Amphi 1	Lecture 1: Introduction (par Luca)	TD 1: Mise en route	mardi 5 janvier
Slides Amphi 2	Lecture 2: Delaunay triangulations and Voronoi diagrams I (par Steve)	TD 2: Shoot'em up! (solution)	mardi 12 janvier
Slides_Amphi_3	Lecture 3: Graphs I: geometric aspects of planar graphs (par Luca)	TD 3: Dessin de graphes  (solution)	mardi 19 janvier
Slides_Amphi_4	Lecture 4: Delaunay triangulations and Voronoi diagrams II (par Steve)	TD 4: Manipulations simples sur les triangulations 3D (solution)	mardi 26 janvier
Slides Amphi 5	Lecture 5: Graphs II: planar separators and applications (par Luca)	TD 5: Codage de graphes (solution: voir la page du TD5)	mardi 2 février
Slides Amphi 6	Lecture 6: Curve and surface reconstruction (par Steve)	TD 6: Reconstruction (solution)	mardi 16 février
Slides Amphi 7	Lecture 7: Geometric proximity problems (par Luca)	TD 7: NN search, Kd-Trees: clustering and image segmentation (solution: voir page TD7)	mardi 2 mars
Slides Amphi 8	Lecture 8: Geometric approximation algorithms I (par Steve)	TD 8: TSP  (solution)	mardi 9 mars
Slides Amphi 9	Lecture 9: Geometric approximation algorithms II (par Luca)	TD 9:  revision	mardi 16 mars

Organisation pratique du cours

Emploi du temps:

Cours en PC18 de 13h30 à 15h et TD en PC18 de 15h15 à 17h15 (mardi après-midi)

• Cours/TDs: 5 janvier, 12 janvier, 19 janvier, 26 janvier, ...
  

Chacun des 9 blocs du cours est constitué d'1h30 en amphi, consacrées au cours, suivies de 2 heures en petite classe, consacrées à la mise en pratique des techniques vues en amphi (sous forme de programmation en Java).

Important: apportez vos portables pour le TD, dès la première séance (le mardi 5 janvier), avec le Java Development Kit version 5 ou supérieure installé.

Librairies utilisées (et à installer):

• Jcg (libraire d'algorithmes géométriques en java, developpée à l'X pour INF562)
  
• java3d (API java pour la création d'applications 3D)
• Jama (Java Matrix Package): librairie pour la manipulation de matrices à valeurs réelles.

Autres programmes utiles:

• Geomview (pour Linux): programme pour visualiser des maillages 3D.

Geomview est disponible aussi sous Windows (voici comment procéder): il faut alors d'abord installer Cygwin.

Propositions de stages (2009-2010)

* COMBINATOIRE ET ALGORITHMIQUE DES GRAPHES PLONGÉS SUR DES SURFACES (pdf, html)
(proposé par Luca Castelli Aleardi et Eric Fusy, LIX, Ecole Polytechnique)

* CODAGES SUCCINCTS EFFICACES DE TRIANGULATIONS ET GRAPHES PLANAIRES (pdf, html)
(proposé par Luca Castelli Aleardi et Gilles Schaeffer, LIX, Ecole Polytechnique)

* RECHERCHE DE PLUS PROCHES VOISINS INVERSES EN GRANDES DIMENSIONS (pdf)
(proposé par Steve Oudot, INRIA Saclay, équipe Geometrica)

La géométrie algorithmique en France et dans le monde

La communauté représente environ une centaine de chercheurs permanents à travers le monde, dont un peu plus d'une vingtaine en France.

Équipes en France :

• Projet Geometrica (INRIA Sophia-Antipolis)
  
• Projet Vegas (LORIA, Nancy)
  
• Equipe Géométrie, Combinatoire et Algorithmes (GéCoaL, ENS Paris)
  
• Equipe Modélisation Géométrique et Multirésolution pour l'Image (MGMI, Grenoble)
  
• Équipe Informatique Géométrique et Graphique (IGG, Université de Strasbourg)
  

Quelques équipes en Europe :

• Algorithms Research Group (ULB, Bruxelles)
  
• Research Group in Computational Geometry and  Combinatorial Geometry (UPC, Barcelona, Spain)
  
• ...

Quelques équipes sur le continent américain :

• Computational Geometry Lab, McGill University (Montréal, Canada)
  
• Computational Geometry Lab, Carleton University (Canada)
  
• Computational Geometry Lab, University of Illinois (Urbana-Champaign, USA)
  
• Computational Geometry Group, UNC (North Carolina, USA), headed by Prof. Jack Snoeyink
  
• Geometric Computing group, Stanford University (California, USA), headed by Prof. Leonidas J. Guibas
  

Page mise à jour le 04/01/2010 par Steve Oudot.