Nos activités de recherche ont trait principalement à la géométrie algorithmique, à la géométrie discrète et à l'optimisation combinatoire. L'accent est mis sur l'étude de problèmes fondamentaux tels que l'étude des arrangements d'hyperplans/droites en géométrie algorithmique ou encore les problèmes de partitionnement de graphes - plus généralement, optimisation dans les espaces binaires - en optimisation combinatoire. L'étude des polyèdres (théorèmes d'universalité, complexité de l'énumération des sommets/facettes), la programmation linéaire (complexité dans le modèle de la RAM réelle, approximation de problèmes combinatoires), pour ne citer que deux exemples, sont des problématiques transversales aux divers domaines d'intérêt et de recherche de notre groupe. Lorsque les problèmes étudiés sont NP-difficiles, notre effort porte sur l'élaboration de méthodes efficaces pour trouver de bonnes solutions approchées ou pour résoudre de façon exacte certaines sous-classes de ces problèmes. Dans le cas des problèmes résolubles en temps polynomial (ce qui est généralement le cas dans la problématique de la géométrie algorithmique) notre objectif est la mise au point d'algorithmes asymptotiquement optimaux, pratiques et simples à mettre en oeuvre. (Notre ambition est de voir nos algorithmes en bonne place dans les bibliothèques d'algorithmes géométriques.) Ce dernier point nécessite un examen attentif des structures de données requises, des primitives de base utilisées, du modèle de calcul, etc. Nos récents succès montrent qu'une étude poussée des aspects mathématiques des problèmes est payante pour l'élaboration d'algorithmes efficaces et pratiques. L'aspect théorique de notre travail de recherche comporte des composantes géométriques, combinatoires et algébriques intervenant tant au niveau des objets et problèmes étudiés qu'au niveau des outils utilisés lors de l'élaboration des méthodes de résolution. Un bon exemple est le problème de la coupe maximale dans un graphe pour lequel le meilleur algorithme approximatif proposé à ce jour repose sur l'utilisation d'un corps convexe composé de matrices positives semidéfinies; un second exemple est le rôle joué par les matroides -- abstraction combinatoire des notions d'espace vectoriel, rang et matrice -- dans l'étude des arrangements d'hyperplans et dans l'étude des notions de coupes/cycles dans les graphes (matroides orientés et binaires, respectivement); enfin citons les problèmes de complétion de matrices (très étudiés en théorie combinatoire des matrices) qui font appel aux polyèdres métriques.
Avant de détailler les pôles principaux de nos activités de recherche nous rappelons brièvement l'historique et le rôle des thèmes de recherche que nous animons au sein du laboratoire. La recherche en géométrie algorithmique est présente au laboratoire depuis sa création en 1986 sous l'impulsion de son premier directeur, C. Puech, en collaboration avec M. Yvinec (CR CNRS). Cette recherche s'est faite pour une part en synergie avec les équipes iMAGIS (graphique et image de synthèse) et PRISME (géométrie algorithmique, robotique) -- la première créée et animée par C. Puech (PR IMAG-INRIA) dans notre laboratoire est basée à Grenoble depuis 1993; la seconde créée et animée par J.D. Boissonnat (DR INRIA) est basée à l'INRIA de Sophia-Antipolis (cette équipe a recruté à ce jour comme CR INRIA trois normaliens, tous trois chercheurs en géométrie algorithmique, et accueille M. Yvinec depuis 1991). Notre groupe conserve avec ces deux équipes des liens privilégiés par le biais d'actions GDR-PRC passées -- qui portent leurs fruits maintenant (deux thèses à ce jour; voir la rubrique Collaborations) -- ou présentes, et par l'animation de la filière Géométrie du DEA Algorithmique cohabilité par l'ENS. La recherche en optimisation combinatoire est présente au laboratoire depuis le recrutement de M. Deza et M. Laurent en 1992. Notre groupe entretient une collaboration privilégiée avec l'équipe de B. Gerards et de A. Schrijver (CWI, Amsterdam) où M. Laurent a passé deux années (94/95 et 96/97, dans le cadre d'une mise à disposition). Cette collaboration a donné lieu à des publications en commun et, par ailleurs, M. Laurent et A. Schrijver ont eu l'occasion de donner un cours d'optimisation combinatoire au Magistère au second semestre 1994. Un des points forts de l'activité du groupe dans ce domaine au cours des quatres années passées a été la rédaction d'un livre intitulé Geometry of Cuts and Metrics par M. Laurent en collaboration avec M. Deza; ce livre est paru chez Springer en Mai 1997 dans la collection Algorithms and Combinatorics [1].
Le calcul de l'orientation d'un simplexe étant l'une des primitives de base des algorithmes géométriques, l'étude de la famille des orientations des simplexes d'une configuration de points a naturellement trouvé sa place au sein de la géométrie algorithmique comme en témoignent les travaux de Goodman & Pollack (types d'ordre) ou de Knuth (CCC systèmes), pour ne citer que les tentatives les plus systématiques. La géométrie algorithmique rejoint ainsi -- parfois sans le savoir -- les prémisses de la théorie des matroides orientés et contribue de manière significative à son développement (nous pensons en particulier au récent théorème d'universalité pour les polytopes de dimension quatre). Via la dualité point-hyperplan (cas particulier du théorème de Folkman-Lawrence sur la représentation des matroides orientés) un type d'ordre -- nous retenons la terminologie introduite par Goodman & Pollack -- est représentable par un arrangement d'hyperplans. L'étude des arrangements d'hyperplans marque ainsi la géométrie algorithmique dès sa naissance et en constitue un chapitre important et toujours actif (théorèmes d'horizon, topological sweep method, k-ensembles, partitions simpliciales, etc.). Notre travail de recherche, dans ce domaine, porte sur l'étude algorithmique et combinatoire des types d'ordre de collections de convexes du plan disjoints deux-à-deux : nous définissons le type d'ordre d'une collection de convexes comme l'arrangement dans le plan projectif des courbes duales des convexes. Cette recherche, initialement motivée par les problèmes de 'visibilité' rencontrés en planification de trajectoires et en informatique graphique, entend enrichir et prolonger l'étude des arrangements de droites ou d'hyperplans. Dans ce cadre général nos contributions portent sur (1) l'algorithmique et la combinatoire des types d'ordre [67, 56] -- notre ambition ici est de développer une théorie axiomatique des types d'ordre de convexes, (2) l'algorithmique des graphes de visibilité [35, 46, 36, 44] -- c'est notre résultat majeur : un algorithme, le Greedy Flip Algorithm, optimal en temps et linéaire en espace de travail pour des convexes quelconques de complexité constante; une première implémentation de cet algorithme est décrite dans [53] et devrait faire l'objet d'une distribution logicielle à court terme; la simplicité conceptuelle et la simplicité de mise en oeuvre de cet algorithme en fait probablement le candidat de choix pour les bibliothèques d'algorithmes géométriques; (3) les problèmes fondamentaux du graphique 2D : lancer de rayon [47, 58], ordre de profondeur [3, 47, 49, 72], radiosité (voir sur ce point l'opération inter-PRC ``Synthèse d'images et Géométrie algorithmique'' dans la rubrique Collaborations) -- l'ensemble de ces travaux s'étale sur la période 92-96; et (4) le type d'ordre du réseau des points entiers [7, 9, 22, 23, 64] (énumération, génération aléatoire et reconnaissance des segments de droites discrètes; bornes inférieures sur le nombre maximal d'incidences entre points et droite, la visibilité dans le réseau unité) -- travaux 88-92 non détaillés dans ce rapport.
Les apports conceptuels de ces travaux se résument en quatre points: introduction de la dualité pseudotriangle/pseudodroite [47, 59, 67], introduction du concept de pseudo-triangulation, introduction du concept de complexe de visibilité [35, 36], unification sous un même formalisme, celui du Greedy Flip Algorithm, de l'ensemble des algorithmes de calcul des graphes de visibilité (Ghosh et Mount, STOC'89/SJC'91) et des algorithmes de calcul des arrangements de droites dont en particulier la Topological Sweep Method, introduite par Edelsbrunner et Guibas (STOC'86/JCSS'89). Dans la mesure où la dualité point-droite ramène le calcul d'un arrangement de droites au calcul du graphe de visibilité d'une configuration de points le Greedy Flip Algorithm se présente a priori comme une alternative à la Topological Sweep Method. A posteriori on peut vérifier que la Topological Sweep Method est une instance du Greedy Flip Algorithm -- techniquement: les arbres d'horizons s'interprêtent en termes de pseudo-triangulations [50, 60]. Il est fort probable qu' il en soit de même pour la Tological Walk Method d'Asano, Guibas et Tokuyama (SoCG'91/IJCGA'94) -- ce point fait l'objet d'un travail en cours. Ces deux dernières techniques fournissent des algorithmes optimaux en temps et en espace pour une grande variété de problèmes : énumérer les faces d'un arrangement d'hyperplans, déterminer les dégénerescences d'une configuration de points, construire les au plus k-niveaux d'un arrangement de droites, etc. Il est probable que le Greedy Flip Algorithm permette d'améliorer l'ensemble de ces algorithmes (simplification conceptuelle, robustesse, etc.) et d'ouvrir de nouvelles perspectives (énumération des triangulations, calcul d'un arrangement d'hyperplans restreint à un domaine convexe, niveaux en dimension 3 et plus, etc.) sur l'algorithmique des configurations de points ou, par dualité, des arrangements d'hyperplans, en dimension 3 et plus.
Un des objectifs majeurs en optimisation combinatoire
est la résolution de problèmes d'optimisation discrète
du type: Etant donnés une famille 
de sous ensembles
d'un ensemble fini E et des poids 
associés aux éléments 
, trouver un ensemble 
de
poids 
maximum. La famille permet d'encoder
diverses notions comme, par exemple, chemins, cycles, arbres,
coupes, circuits Hamiltoniens, etc., dans les graphes
et ce problème très général s'applique à une grande diversité de situations
concrètes. Par exemple, lorsque est la famille des coupes d'un graphe, on
trouve le
problème de la coupe maximale dans un graphe,
qui a de nombreuses applications, par exemple,
en physique statistique, VLSI design, etc. (cf.
[15, 16]); ce problème
est un des
problèmes NP-difficiles de
base de l'optimisation combinatoire,
dont la complexité avait été analysée dans
l'article fondateur de Karp (1972).
Une des méthodes classiques de résolution, qui s'appuie
sur la combinatoire polyédrale et la programmation linéaire,
repose sur l'étude d'un polyèdre associé (le polyèdre défini
comme l'enveloppe convexe dans l'espace 
des vecteurs d'incidence des membres de )
et des relaxations linéaires de ce polyèdre. Dans ce
contexte nous avons étudié de façon intensive
le polyèdre des coupes d'un graphe dans des travaux antérieurs
à la période 1994 non détaillés ici; ces travaux
sont repris en partie dans le livre [1].
Nous nous sommes intéressés récemment à une nouvelle approche pour trouver de bonnes solutions approchées, notamment, la programmation semidéfinie qui consiste à approximer le polyèdre en question par un corps convexe (en général, non polyédral) sur lequel on sait optimiser en temps polynomial (en utilisant, par exemple, des algorithmes de type `interior-point'). Dans le cas du problème de la coupe maximale, le corps convexe en question (appelé elliptope) est l'ensemble des matrices carrées positives semidéfinies avec entrées diagonales toutes égales à l'unité. Avec S. Poljak, nous avons introduit l'elliptope dans [25] et développé une étude systématique de ses propriétés, en particulier, d'un point de vue géométrique dans [27, 28, 24]. Nous montrons que l'elliptope a des sommets qui coincident avec ceux du polyèdre qu'il approxime et qu'il partage également de nombreuses faces communes. Ces faits géométriques permettent de mieux comprendre les propriétés remarquables de l'elliptope. En effet, Goemans et Williamson ont montré que l'elliptope permet d'obtenir un algorithme d'approximation pour la coupe maximale avec une performance de 13% (alors que le meilleur algorithme approximatif connu jusqu'alors pouvait garantir au mieux une erreur de 50%). Nous démontrons une meilleure performance pour certaines fonctions objectives. Par ailleurs, nous montrons dans [24] le lien existant entre l'elliptope et le corps convexe utilisé dans le travail de Grötschel, Lovász et Schrijver pour l'approximation de la clique maximale dans un graphe. Nous y expliquons également comment l'elliptope peut être utilisé pour un problème quelconque de programmation en nombres entiers.
L'elliptope intervient aussi dans le problème d'algèbre linéaire concernant la complétion des matrices positives semidéfinies, traité ci-dessous.
D' autres travaux sont consacrés aux
coupes dans les graphes et à leurs liens
avec diverses questions, comme les questions de plongements
isométriques dans l'hypercube ou dans l'espace
rectilinéaire (i.e., muni de la métrique 
) [17, 18, 40],
les inégalités hypermétriques et les polyèdres de Delaunay
dans les réseaux [4].
Le livre [1]
réalise une présentation détaillée sur ce
sujet et une bibliographie détaillée pour le
problème de la coupe maximale est donnée dans [2].
Le problème de complétion de matrices est le suivant:
Etant donnée
une matrice dont les entrées sont partiellement
spécifiées, décider si l'on peut compléter les entrées
manquantes de
telle sorte que la matrice obtenue ait une certaine popriété.
Nous nous intéressons au cas où la propriété requise
est celle d'être une matrice
positive semidéfinie ou encore une matrice de distances Euclidiennes.
Rappelons qu'une matrice 
est dite de distances
Euclidiennes
si il existe des vecteurs 
tels que chaque entrée
est égale au carré de la distance Euclidienne entre
et 
.
Si l'on fixe la dimension de l'espace où l'on cherche les
vecteurs
permettant de compléter la matrice partielle, le problème
est NP-difficile et a de nombreuses et
importantes applications; par exemple, en chimie moléculaire,
où on essaie de reconstruire la forme d'une molécule à partir
de données incomplètes concernant les distances entre les
atomes la composant. On note que le problème de tester
si une matrice partielle est complétable en une matrice
positive semidéfinie revient, en fait, au problème de
trouver de bonnes caractérisations des projections de l'elliptope
(soit la relaxation permettant de bonnes approximations
pour le problème max-cut) et peut etre résolu
par les techniques de la programmation semidéfinie.
Nous avons travaillé sur les problèmes de complétion dans les articles [32, 5, 41, 33]. En particulier, nous avons trouvé de nouvelles conditions nécessaires devant être satisfaites par les entrées de la matrice partielle pour qu'elle soit complétable; ces conditions font appel aux polyèdres de coupes et métriques, ce qui établit un lien entre des objets utilisés en optimisation combinatoire et la théorie combinatoire des matrices. Egalement, nous avons montré comment - en utilisant une extension de certains résultats de Schoenberg - les résultats concernant les matrices de distances Euclidiennes découlent simplement de ceux concernant les matrices positives semidéfinies. Nous réalisons dans [5] un survol de l'état des connaissances dans le domaine et dans [41] nous faisons le lien avec les questions de rigidité pour les graphes.
La notion combinatoire de matroide permet
de modéliser une grande variété de structures, telles que
les arrangements d'hyperplans (matroides orientés),
ou les arbres, cycles et coupes dans les graphes (matroides
binaires). Les matroides représentent
un cadre très général pour la validité de nombreux résultats et,
bien souvent, il est conceptuellement plus simple de travailler
à ce niveau de généralité sans être encombré des particularités propres
aux divers exemples.
Comme mentionné plus haut, un des problèmes de base en optimisation combinatoire
est de trouver la description par un système d'inégalités linéaires
pour un polyèdre dont les sommets sont des vecteurs entiers specifiés.
Dans ce cadre se pose la question: Etant donnés une matrice A et un vecteur b,
décider si tous les sommets du polyèdre 
sont entiers.
Nous nous sommes intéressés aux versions suivantes
de ce problème où A et b sont définis à partir de
matroides.
Considérons les polyèdres 
et
associés au port 
d'un matroide binaire (i.e.,
consiste des circuits passant par un élément donné;
par exemple,
est l'ensemble
des chemins joignant deux points dans un graphe).
Une question fondamentale, liée à la théorie
des multiflôts, est la caractérisation des familles de ports
pour lesquelles
tous les sommets du polyèdre 
sont entiers.
Seymour a caractérisé les ports
de matroides binaires pour lesquels le polyèdre
est totalement dual intégral, ce qui est une
propriété
plus forte.
Avec B. Gerards, nous caractérisons dans [20]
les ports de matroides binaires
pour lesquels tous les sommets de 
ont
dénominateur
d pour tous choix de a,b avec dénominateur d ( 
);
ceci
généralise un résultat
de [26] pour les graphes. Le cas d=1, qui correspond
à la
situation où le polyèdre est entier,
fait l'objet d'une conjecture de Seymour non résolue à ce jour.
Le cône entier 
intervient naturellement dans
divers problèmes, par exemple, pour l'étude des métriques
plongeables dans l'hypercube si le port
est la famille des coupes d'un graphe.
On rappelle que forme une base de Hilbert si
consiste des points appartenant simultanément au
réseau 
et au cone 
.
Les graphes dont la famille des circuits est une base
de Hilbert ont été caractérisé par
Alspach, Goddyn et Zhang (le graphe de Petersen est le seul
mineur exclu).
L'article [31] donne des résultats
pour le problème dual, i.e., sur les
graphes dont la famille de
coupes est une base de Hilbert; nous montrons, en particulier,
que 
est un mineur exclu.
Dans [57] nous nous intéressons au problème de trouver une base
courte
dans le réseau entier
où est la famille des cycles d'un
matroide
binaire.
Nous montrons que pour les matroides sans mineur 
et leurs
extensions par un élément
en série on peut construire une base dont tous les vecteurs sont
binaires et donc très courts.
Les polytopes de Delaunay sont des objets importants en géométrie algorithmique et en géométrie des nombres. Un résultat d'Assouad montre que tout polytope de Delaunay P peut être interprété comme un point d'un certain cône (le cône hypermétrique), ce qui permet de définir une notion de rang pour P. Nous montrons dans [29] que ce rang coincide avec une autre notion géométrique, la dimension du groupe des transformations linéaires qui envoient P sur un autre polytope de Delaunay. Nous réalisons dans [4] un survol détaillé des liens entre polytopes de Delaunay et cône hypermétrique.
Un résultat classique de Menger montre que l'on peut tester
en temps polynomial si un espace métrique
est plongeable dans l'espace Euclidien de dimension m fixée;
il suffit en effet de le vérifier pour tous les sous espaces à
m+3 points.
Bandelt et Chepoi ont montré un résultat analogue pour l'espace
rectilinéaire
de dimension 
. Une question qui se pose dans ce contexte
est la détermination
du nombre maximum de points équidistants dans l'espace
rectilinéaire de dimension
m, conjecturé égal à 2m. Ce nombre est confirmé dans
[6] pour 
.
Avec H. van der Holst et A. Schrijver, nous
étudions dans [39]
un nouvel invariant pour les graphes, en partie motivé
par le travail d'Y. Colin de Verdière.
Etant donné un graphe G=(V,E),
soit 
le
plus grand entier d pour lequel il existe un
sous espace 
de dimension d tel que le
support
positif de tout vecteur 
induise un sous graphe connexe
de G.
Comme est monotone
pour les opérations de mineur,
la classe des graphes G pour lesquels
peut être caractérisée par un nombre
fini de configurations interdites.
Nous montrons dans [39] que 
si et seulement si G peut être construit à
partir des graphes planaires par application des opérations de
clique-sommes et sous-graphes; il y
a exactement deux configurations minimales interdites.
Nous étudions dans [19] une extension du paramètre
dans le contexte des matroides orientés.
Les perspectives d'évolution, relativement à court terme, de notre travail en géométrie algorithmique tournent autour des thèmes : Algorithmes de balayage -- Robustesse des algorithmes de balayage -- Triangulations versus pseudo-triangulations -- Axiomes et graphes de visibilité ou Axiomes et types d'ordre -- Production et diffusion de logiciels (notre ambition est de participer au développement de bibliothèques d'algorithmes géométriques). A plus long terme deux objectifs : une relecture de la géométrie algorithmique certainement très fructueuse après la période de fondations et d'investigations théoriques intenses que le domaine à connu ces dix dernières années, et développement de travaux appliqués (frotter les acquis du domaine à la pratique du calcul géométrique).
Notre recherche s'orientera aussi sur la programmation semidéfinie (dans la perspective de ses applications à l' optimisation combinatoire et aux problèmes de complétion de matrices) et sur les questions liées aux matroides binaires, deux thèmes qui ont connu récemment de fructueux développements. Un de nos projets est la rédaction d'un ouvrage de synthèse sur ce dernier thème, avec pour objectif une présentation unifiée des résultats de base sur les enveloppes de cycles dans les espaces binaires. Nous comptons poursuivre notre collaboration avec le CWI, en particulier, en rapport avec ce dernier projet de travail sur les espaces binaires.
Il reste par ailleurs de nombreuses questions ouvertes dans notre travail actuel sur lesquelles nous comptons poursuivre notre effort (e.g., la recherche de bonnes bases dans les réseaux de cycles, en particulier pour les matroides dits 'Euleriens' considérés par Lovász et Seress, analogue du théorème de Menger pour les espaces rectilinéaires, étude de paramètres géométriques pour les graphes).
M. Pocchiola a participé plus particulièrement aux recherches du thème ``Algorithmique géométrique" de l'opération. Ses travaux sur la visibilité (Introduction du concept de Complexe de Visibilité) ont permis à ce thème d'influencer l'activité de certains autres thèmes tel celui du ``rendu" : problèmes de visibilité en simulation de l'éclairage. Cette influence s'est concrétisée, au sein de l'équipe Imagis dirigée par C. Puech à Grenoble, par la soutenance de deux thèses en 97 (une troisième prévue en 98), la production de trois vidéos, de quatres articles et deux posters dans des conférences internationales (ACM-SoCG'95/96/97, ACM-WoACG'96, SIGGRAPH'97, Eurographics'96).
Elle a également organisé une des sessions parallèles lors des 15ème et 16ème symposia ``Mathematical Programming'' de Ann Arbor (Août 94) et Lausanne (Août 97).
Livres
Chapitres de livres
Articles invités
Articles dans des revues internationales avec comité de lecture
-rigid graphs.
Journal of Algebraic Combinatorics, 3:153-175, 1994.
-nets and alternating form graphs.
Discrete Mathematics, 114:237-252, 1993.
Conférences invitées
Communications dans des conférences internationales avec comité de lecture
Autres conférences
Thèses
Articles soumis ou en préparation
Rapports du DMI
-embeddability and
probability.
Rapport LIENS-93-17, Ecole Normale Supérieure (Paris), 1993.
Rapports de recherche publiés dans d'autres laboratoires
Oeuvres de vulgarisation scientifique