Direction des Relations et Internationales (DRI)

Programme INRIA "Equipes Associées"





Equipe-Projet INRIA : Géometrica Organisme étranger partenaire : Stanford University
Centre de recherche INRIA : Futurs / Saclay
Thème INRIA : SYM (systèmes symboliques)
Pays : USA
Coordinateur français
Coordinateur étranger
Nom, prénom OUDOT, Steve Y. GUIBAS, Leonidas J.
Grade/statut CR / Chargé de Recherches Full Professor
Organisme d'appartenance
(précisez le département et/ou le laboratoire)
INRIA Futurs Stanford University, Computer Science Department
Adresse postale Parc Orsay Université
ZAC des Vignes
4, rue Jacques Monod - Bât. P
91893 ORSAY Cedex, France
Computer Science Department
Gates Building
Stanford University
Stanford, CA 94305, USA
URL tba
Téléphone (+33) 174 854 216 (+1) 650 723 0304
Télécopie (+33) 174 854 249 (+1) 650 723 0033
Courriel steve.oudot[at] guibas[at]

La proposition en bref / Overview of the Proposal

Collaboration title: Topological and Geometric Data Analysis / Analyse topologique et géométrique de données

Description (about 10 lines) :

TGDA is an associate team between the Géometrica group at INRIA and the Geometric Computation group at Stanford University, focused on the topological and geometric analysis of possibly high-dimensional point cloud data that are difficult to handle with standard linear or non-linear dimensionality reduction techniques. Such data appear in as diverse areas as machine learning, dynamical systems, structural biology, image processing, or sensor networks. They are typically obtained by sampling from highly-curved manifolds with non-trivial topology, embedded in high-dimensional Euclidean spaces. Our main goal will be to devise suitable methods to handle this type of data, based on recent advances in computational geometry and algebraic topology, including (but not restricted to) persistent homology, witness complexes, and distance functions. Both the Géometrica group at INRIA and the Geometric Computation group at Stanford University have actively contributed to these advances in the recent years, and we think their collaboration is now mature enough to take advantage of the associate team framework. To validate our approach, we intend to set our methods against real-life data sets coming from other scientific fields, thereby developing new collaborations with other groups at INRIA and at Stanford University.


II. BILAN 2008


Rapport scientifique de l'année 2008

The research program for 2008 is accessible here

Throughout the first year of existence of TGDA, priority has been given to the development of new collaborations between the two research groups. The aim was to create opportunities for members from both groups to interact with one another. From a practical point of view, this strategy encouraged visits and student exchanges greatly. From a scientific point of view, it created a real synergy between the two groups, whose respective expertises in the area of point cloud data analysis turned out to be quite complementary. In terms of scientific outcomes, emphasis has been put on the following theoretical questions raised by or closely related to the 2008 research program:

In parallel, some members of TGDA have investigated more algorithmic questions related to the research project, among which the following one is of major practical interest:

Rapport financier 2008

Certaines dépenses sont encore prévisionnelles à ce stade. Leurs montants exacts seront ajustés en fonction du budget restant sur TGDA.

1. Dépenses EA (effectuées sur les crédits de l'Equipe Associée)
Montant dépensé
Invitations des partenaires 11,626.22
Missions INRIA8,517.72
2. Dépenses externes (effectuées sur des financements hors EA)
Montant dépensé
Région PACA:
Invitations des partenaires 0
Missions INRIA vers le partenaire 1,800 (bourse de 600 euros/mois allouée à Quentin Mérigot)
NSF grants:
Invitations des partenaires 0
Missions INRIA vers le partenaire 18,000
NSF REUSSI program:
Invitations des partenaires 1,500
Missions INRIA vers le partenaire 0
Invitations des partenaires 1,500
Missions INRIA vers le partenaire 0

Total des financements externes dépensés


Total des financements EA et externes dépensés



Bilan des échanges effectués en 2008

As both parties were willing to develop new collaborations, exchanges within the TGDA project have been pretty numerous and productive during this first year, both at junior and senior levels:

1. Chercheurs Seniors

statut (1)
objet (2)
durée (3)
Coût (si financement EA)
Coût (si financement externe)
Steve Oudot CR INRIA Stanford visite 5 mois 1,069.79 13,760
Steve Oudot CR Stanford INRIA réunion de travail 7 jours 1,156.19 0
Frédéric Chazal DR INRIA Stanford visite 14 jours 1,166.14 1,600
David Cohen-Steiner CR Duke Stanford visite 7 jours 500 840
Leonidas Guibas Professeur ETH INRIA visite 7 jours 1,200 0
Steve Oudot CR INRIA New York conférence SODA 7 jours 1,900 0

Total des durées
  6 mois 11 jours
(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....
précisez l'unité (mois, semaine..)

2. Juniors

statut (1)
objet (2)
durée (3)
Coût (si financement EA)
Coût (si financement externe)
Quentin Mérigot doctorant INRIA Stanford visite 3 mois 2,725.60 3,600
Maksim Ovsjanikovs doctorant Stanford INRIA visite 2 mois et demi 3,750 3,000
Primoz Skraba doctorant Stanford INRIA visite 2 mois et demi 6,676.22 0

Total des durées
  8 mois
(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)


Programme de travail

While the collaboration between the two research groups was initiated around the more theoretical aspects of the 2008 research project, a great deal of our efforts in 2009 will be geared towards more practical questions, as we believe the tools developped in 2008 have a high potential for applications. To this end, we will need to develop methods that can perform some of the steps of our algorithms efficiently, including finding reverse nearest neighbors to update our data structures, or computing persistent homology to get their associated persistence barcodes. Meanwhile, we intend to pursue our efforts towards developing a geometric and topological inference theory for sampled spaces, in order to strengthen the positions of both groups as leaders in the area.

1. Applications

2. Algorithmic aspects

3. Theoretical aspects


Programme d'échanges avec budget prévisionnel

1. Echanges

Interactions and collaborations within the TGDA project have been very active throughout 2008. We will try our best to keep them at a comparable level in 2009:

In addition to the above exchanges, Vin de Silva will visit the Geometrica group for a 6-months period, from January to June 2009 (his expenses will be covered by other grants). His visit will strengthen the associate team and help greatly in the investigation of the more theoretical aspects of our research program. Moreover, as one of the pioneers of the Computational Topology library PLEX, developped and maintained by the Applied Topology group at Stanford, Vin de Silva will act as a cornerstone in the establishment of a long-term collaboration between this group and TGDA around the development of the library, which in the longer run is likely to become a reference in the field.

Finally, TGDA intends to organize a mini-workshop, to be held in Saclay and/or Paris around early July 2009. This event is motivated by the promising results that were obtained during the first year of the collaboration, and by their expected outcomes in terms of applications. The format of the workshop is still to be discussed, but organizers agree on a 2+1 days structure: 2 days for formal talks and demos to a broad audience, plus 1 day for internal discussions among the members of TGDA about future directions and code development issues.

Nombre de personnes
Coût estimé
Chercheurs confirmés 4 12,000
1 1,500
Doctorants 2 10,000


Autre (précisez) :


Nombre de personnes
Coût estimé
Chercheurs confirmés 2 6,000
1 2,500
Doctorants 2 10,000


Mini-workshop :
logistique sur place + invitations 10,000

2. Cofinancement

3. Demande budgétaire

Indiquez, dans le tableau ci-dessous, le coût global estimé de la proposition et le budget demandé à la DRI dans le cadre de cette Equipe Associée.
(maximum 20 K€ pour une prolongation en 2e année et 10 K€ pour une 3e année).

A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...)   52,000
B. Cofinancements utilisés (financements autres que Equipe Associée)   32,000

Financement "Équipe Associée" demandé (A.-B.)
(maximum 20 K€ pour une 2e année et 10 K€ pour une 3e année)




© INRIA - mise à jour le 16/10/2008