L'explosion de la puissance de calcul permet actuellement de réaliser des simulations physiques comportant jusqu'à plusieurs milliards d'éléments. Pour extraire l'information importante de tels volumes de données, les ingénieurs doivent disposer d'outils de visualisation permettant d'explorer et d'analyser interactivement les champs calculés. Cette thèse vise à améliorer les visualisations réalisées en prenant en compte les caractéristiques de la perception visuelle chez l'homme, notamment en ce qui concerne la perception de l'espace et du volume au cours de visualisations 3D denses. D'abord, trois expériences de psychophysique ont montré que les rendus volumiques, reposant sur l'accumulation ordonnée de transparences, génèrent des difficultés importantes de perception de la profondeur. Cela est particulièrement vrai lors de visualisations statiques, mais l'ajout de mouvement dans la scène ainsi que l'amplification de la projection perspective permettent de lever en partie ces ambiguïtés. Ensuite, deux algorithmes améliorant la perception de l'espace lors de la visualisation de structures tridimensionnelles complexes ont été développés. Leur implémentation sur GPU permet des rendus interactifs indépendamment de la nature géométrique des données visualisées. L'EyeDome Lighting, un nouvel ombrage non photoréaliste basé sur l'image de profondeur, améliore la perception des formes et des profondeurs dans des scènes 3D complexes. Par ailleurs, une nouvelle technique d'écorché dépendant du point de vue a été implémentée. Elle autorise la visualisation d'objets normalement occultés tout en rendant compte de la structure des surfaces masquantes.

Le squelette de visibilité est une structure de donnée qui encode l'information de visibilité globale pour une scène donnée en 2D ou 3D. Cette structure de donnée est en principe très utile pour répondre à des requêtes de visiblité globale, mais elle est, en particulier en 3D, d'une complexité de haut degré dans le pire des cas qui semble prohibitive. Cependant, les recherches théoriques précédentes ont indiqué que l'espérance de la taille de cette structure de donnée peut être linéaire sous certaines conditions restreintes. Cette thèse approfondit l'étude de la taille du squelette de visibilité, au moyen d'une approche expérimentale. Nous montrons d'abord qu'aussi bien théoriquement qu'empiriquement, l'espérance de la taille du squelette de visibilité en 2D est linéaire, et présentons une asymptote affine qui facilite l'estimation de la taille du squelette de visibilité en 2D. Nous étudions ensuite le squelette de visibilité 3D défini par événement visuels, qui est un sous-ensemble du squelette complet défini par Durand et al. . Nous présen- tons tout d'abord une implantation calculant les sommets de ce squelette pour des polytopes convexes disjoints en position générale. Cette implantation nous permet de continuer notre étude empirique en 3D. Nous considérons des scènes données consis- tant en des polytopes convexes disjoints qui sont une approximation de sphères unités distribuées aléatoirement. Nous avons découvert que, dans ces conditions, la taille du squelette de visibilité 3D a une relation quadratique en le nombre de polytopes donnés, et linéaire en l'espérance de la taille de la silhouette des polytopes donnés. Cette estimation est bien plus basse que la complexité dans le pire des cas, mais plus haute que la complexité linéaire que nous espérions initialement. Nous présentons aussi des arguments qui pourraient expliquer la complexité obtenue. Nous prouvons finalement qu'en utilisant le squelette de visibilité 3D défini par événement visuels, nous pouvons calculer les sommets restants du squelette complet en temps presque linéaire en la taille du résultat.

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots.<br /><br />Les algorithmes randomisés ont été un des sujets ``chauds'' de ces dernières années et nous proposons ici des travaux ayant trait à des algorithmes dynamiques ou semi-dynamiques : tout d'abord un schéma général d'algorithmes semi-dynamiques avec des applications aux diagrammes de Voronoï, aux diagrammes de Voronoï d'ordre k aux arrangements, et ensuite deux algorithmes dynamiques (permettant d'insérer et de supprimer des données) pour la triangulation de Delaunay et le calcul d'un arrangement de segments. D'autres résultats concernent des algorithmes statiques, notamment le calcul du squelette d'un polygone simple en temps O(n log* n).<br /><br />La deuxième partie explore différentes modélisations des sphères. On peut en déduire notamment un algorithme en O(tk log n) pour la triangulation de Delaunay de n points appartenant à k plans en 3 dimensions, si t désigne la taille du résultat; dans la cas de deux plans cet algorithme atteint une complexité optimale de O(t+n log n). Nous proposons également un algorithme de complexité O(n^ ceil(d/2) +n log n) pour le calcul de l'enveloppe convexe de n sphères en dimension d, et un algorithme optimal (quadratique) pour le calcul de la surface de Connolly.<br /><br />La dernière partie traite de problèmes spécifiques à la planification de trajectoires, un premier chapitre concerne le cas de plusieurs robots polygonaux en translation dans le plan: certaines configurations appellées double-contacts peuvent jouer un rôle particulier dans certains cas. Ensuite deux résultats à propos de robots à pattes : l'analyse d'un cas simple que nous avons baptisé robot araignée, et l'étude de la stabilité d'un robot un peu plus complexe.

Nos travaux s'inscrivent dans la discipline de l'interaction homme-machine (IHM), et concernent l'utilisation d'une nouvelle " forme " de systèmes informatiques : les tables interactives ou " tabletop ". Les systèmes tabletop prennent la forme d'une table dans son entier, qui sert à la fois de périphérique d'entrée tactile et de périphérique de sortie graphique. Grâce aux technologies multi-tactile, plusieurs utilisateurs peuvent toucher la table en même temps, et interagir avec le système de façon indépendante. Cette propriété rend les tables interactives particulièrement adaptées au support de la collaboration. Pourtant, nous constatons que les tables interactives ne sont que peu utilisées dans un objectif collaboratif en dehors des laboratoires. Nous pensons que plusieurs causes permettent d'expliquer cet état de fait. Nous remarquons, d'une part, que les applications existantes, pour ordinateurs de bureau, forment une part importante de l'utilisation actuelle des systèmes informatiques. Ces applications, qu'elles soient des applications grand public largement utilisées ou des applications spécifiques à une tâche précise, sont indispensables à leurs utilisateurs. Des projets ont créés des nouvelles applications aux mêmes fonctionnalités que les applications existantes, mais adaptées à des prototypes de nouveaux systèmes d'interaction. Elles offrent nettement moins de fonctionnalités que les applications pour ordinateurs de bureau existantes. Une telle réécriture reste de plus coûteuse au regard des efforts de développement déjà investis dans la création des applications existantes. D'autre part, les tables interactives se présentent sous un aspect matériel différent des ordinateurs traditionnels, au-delà du trio écran-clavier-souris. Cela introduit de nouvelles possibilités mais aussi de nouveaux défis pour l'interface utilisateur des applications. En revanche, les besoins des utilisateurs, en termes de fonctionnalités des applications, restent les mêmes. Nous étudions comment ce changement peut se répercuter sur les applications existantes. Nous proposons d'utiliser les mêmes applications sur la table interactive que sur l'ordinateur de bureau. Plusieurs types d'interactions sont envisageables pour remplacer les styles d'interaction de l'ordinateur de bureau qui ne sont pas adaptés aux systèmes tabletops. Nous entrons ici dans le domaine des interactions post-WIMP, des interactions qui vont au-delà des interacteurs 2D classiques que sont les fenêtres, les icônes, les menus et le pointeur (WIMP : Windows, Icons, Menus, Pointer). Les applications pour tables interactives ne se programment pas de la même manière que les applications pour ordinateurs de bureau. Nous évaluons six technologies permettent faire le lien entre les techniques utilisées pour programmer des applications pour ordinateurs de bureau et les techniques utilisées pour programmer des applications pour tables interactives : capture d'écran, carte graphique virtuelle, clavier virtuel et souris virtuelle, langage de script, API d'accessibilité numérique, réécriture d'une boîte à outils d'interface homme machine. Pour les évaluer, nous définissons cinq axes (structuration des données, flexibilité, performance, compatibilité et réutilisabilité, et difficulté d'implémentation). Nous avons implémenté des prototypes pour la carte graphique virtuelle, le langage de script, et la réécriture d'une boîte à outils (la boîte à outils win32). Les applications pour tables interactives ne s'utilisent pas de la même façon que les applications pour ordinateurs de bureau non plus. Les interfaces utilisateur des applications existantes ont été conçues pour être utilisées par un seul utilisateur avec un ordinateur de bureau. Les technologies que nous avons présentées ne résolvent pas ce problème. Nous présentons des scénarios mettant en évidence ces limitations. Pour concevoir de nouvelles techniques d'interaction adaptées, nous introduisons la métaphore du papier. Les métaphores sont utilisées, en interaction homme-machine, pour aider les utilisateurs à appréhender le fonctionnement d'un nouveau système plus rapidement en y appliquant des connaissances d'un système qu'ils connaissent déjà. Le papier, probablement le support d'information le plus courant, offre de nombreuses possibilités d'interaction. Nous proposons ainsi trois techniques d'interaction inspirées du papier. Nous proposons des fentes qui permettent de transmettre à distance des documents à un autre utilisateur, ainsi que d'effectuer des traitements sur les documents. Le pliage durable permet de nouvelles interactions avec un document. Il rend accessible le dos du document, qui peut contenir une interface graphique pour l'utilisateur. En observant le recto de documents papier existants, nous sommes arrivés à la conclusion que certains artefacts informatiques existants auraient toute leur place au dos d'un document : le système d'aide de l'application, des outils pour gérer le cycle de vie du document, des métadonnées sur le document,... Enfin, le plier pour empiler permet la création de piles de façon spontanée, en " recyclant " un document existant comme couverture pour de pile, simplement en le pliant en deux. Certaines des interactions peuvent être effectuées de plusieurs manières. Nous proposons un formalisme que nous appelons matrice des interactions, dédié aux interactions de gestion des documents sur la surface d'une table interactive, pour les comparer. Nous nous basons sur les interactions déjà existantes dans la gestion des fenêtres sur les ordinateurs de bureau : le déplacement et le redimensionnement, auxquelles nous ajoutons trois interactions : la rotation, le zoom et le pliage. Ces interactions s'approchent de devenir des standards en matière d'interface pour table interactive dans la communauté des tabletops. Nous avons identifié trois moyens distincts d'effectuer ces cinq interactions : l'utilisation d'un interacteur dédié, l'utilisation de la position du document sur la table, et l'utilisation de la trajectoire du doigt de l'utilisateur. Notre matrice met en évidence que ces trois moyens peuvent être proposés simultanément par le système informatique, imitant ainsi cette propriété du monde physique.

Ce mémoire résume ma contribution aux problèmes de la représentation et de la comparaison des formes et propriétés chimiques de molécules au moyen de nouvelles techniques de transformées de Fourier rapides (FFT). Les trois principaux domaines abordés ici sont le clustering et la classification des formes de macromolécules protéiques, le docking ou amarrage protéine-protéine visant à modéliser la conformation structurale de deux partenaires susceptible d'exister in vivo, et enfin la comparaison rapide de nombreuses petites molécules pour le criblage virtuel de potentiels inhibiteurs thérapeutiques. Les techniques basées sur la FFT sont largement utilisées dans de nombreux domaines de la science. Par ailleurs, les approches conventionnelles basées sur les grilles cartésiennes de FFT peuvent accélérer les calculs d'appariement moléculaire dans seulement trois des six degrés de liberté (ceux de translation) du corps rigide. Le thème principal de mon travail repose sur l'idée que la comparaison des formes complexes en trois dimensions (3D) de molécules est en grande partie un problème de rotation, dès lors les molécules peuvent efficacement être représentées par des systèmes de coordonnées polaires afin de pouvoir les comparer à l'aide de FFT rotationelles. Dans ce mémoire, je montre qu'en représentant les molécules par des développements orthogonaux en harmoniques sphériques et des polynômes de Gauss-Laguerre et en n'utilisant que des techniques classiques de calcul, leurs formes peuvent être mises en rotation et translatées analytiquement. Les paires de formes peuvent alors être comparées ou amarrées de façon très efficace en utilisant une série de 1D, 3D, ou même 5D FFT de rotation. Même si une grande partie des fondamentaux théoriques sont bien connue dans les domaines de la chimie ou de la physique, l'approche globale est originale dans le contexte de l'appariement de formes moléculaires, du docking de protéines et plus généralement de la reconnaissance d'objets 3D. La dernière partie de ce mémoire ouvre sur les perspectives futures visant à étendre ces différentes approches aux défis actuels posés par la biologie systémique et structurale tels que le criblage virtuel à haut-débit, l'intégration de la flexibilité des protéines lors de leur complexation mais aussi l'assemblage de structures macromoléculaires multi-composants.

Les developpements de specifications et des preuves formelles ont pris de l'ampleur durant les dernieres decennies, elabores au sein d'une diversite de canevas, de systemes et de communautes. Cependant l'heterogeneite de ces environnements gene quelques-unes des etapes fondamentales du processus de reflexion scientifique : le partage et la reutilisation des resultats. Cette dissertation propose une methode de distribution du meme developpement formel entre de divers systemes de preuve, augmentant ainsi eur interoperabilite. es chapitres 1 et 2 presentent le cadre logique qui est employe pour centraliser les specifications et les preuves formelles. Sa principale contribution est une ariation du λµ˜ µ-calcul conçu pour supporter le eveloppement interactif de preuves. Les chapitres 3 et 4 developpent les structures de recriture et categoriques necessaire a l'expression formelle de la semantique des langages de preuve. Base sur ces premiers resultats, le chapitre 5 utilise un systeme de types pour des langages de preuve pour asseoir un propriete de surete de typage, et le chapitre 6 expose une serie de traductions des developpements centralises dans d'autres cadres formels majeurs. Entre autres, le dernier contribue a une simplification des systemes de deduction a la Frege-Hilbert. En conclusion, les chapitres 7 et 8 s'interessent aux problemes resultant de l'implementation de notre systeme de developpement centralise de preuve. Ainsi, celui-ci decrit les details du logiciel cree, et celui-la fait la presentation d'une theorie de classes qui permet l'expression finie au premier ordre de schemas d'axiomes.

Cette these traite de l'algorithmique des cartes planaires (graphes dessines dans le plan sans intersection d'aretes) et propose des procedures efficaces pour le codage, la generation aleatoire, et le dessin de plusieurs familles importantes: 3-connexes, triangulations, quadrangulations... En particulier, on decrit le premier algorithme optimal de codage des incidences faces-aretes-sommets des maillages polygonaux de topologie spherique, qui atteint la borne inferieure de 2bits par arete. En partant d'un generateur de cartes 3-connexes, on developpe un nouveau generateur aleatoire uniforme de graphes planaires dont la complexite est la meilleure connue actuellement: quadratique (en esperance) en taille exacte et lineaire (en esperance) en taille approchee. Enfin, on donne plusieurs algorithmes de dessin en lignes droites (aretes representees par des segments) de cartes planaires sur la grille. Les procedures de dessin sont a la fois tres simples a decrire et donnent les meilleures performance (en probabilite) pour le dessin de deux familles de cartes: les triangulations du carre sans 3-cycle rempli —dite irreductibles— et les quadrangulations. Pour developper les algorithmes presentes dans la these, on exploite plusieurs structures combinatoires sur les cartes (orientations specifiques, partitions en arbres couvrants...) ainsi que de nouvelles constructions bijectives.

Cette thèse développe une approche originale de l'interprétation interactive de la théorie de la démonstration en logique linéaire. À l'inverse du cadre joueur/opposant communément associé aux sémantiques des jeux pour la logique, nous proposons un modèle dans lequel les deux joueurs ont des rôles symétriques. Plus précisément, nous passons d'une situation dans laquelle un joueur tente de démontrer un énoncé tandis que l'autre tente de le réfuter à une situation dans laquelle les deux joueurs tentent de démontrer des énoncés contraires. Dans la tradition du calcul vu comme comme recherche de démonstrations, chaque étape de l'interaction est vue comme une étape de deux recherches de démonstrations orthogonales en calcul des séquents. Ce travail contribue dans une certaine mesure à formaliser les liens entre la recherche de démonstrations et la normalisation de démonstrations. Nous présentons d'abord un jeu symétrique simple pour le fragment additif de la logique linéaire, en guise d'introduction à la recherche duale de démonstrations. Nous passons ensuite à un jeu symétrique bien plus complexe pour le fragment additif et multiplicatif de la logique linéaire. Afin d'obtenir un résultat de pleine complétude, nous développons ensuite un troisième jeu à la fois symétrique et concurrent. Enfin, nous étudions quelques extensions de notre modèle.

Ce document présente une synthèse des activités de recherche que j'ai menées depuis dé- but 2002 sur les mesures non additives. J'ai choisi, par souci de clarté, de présenter en détails les résultats concernant l'interprétation et l'identication de mesures non additives obtenus dans le cadre de diverses collaborations et de ne décrire que succinctement les recherches connexes que je mène de façon moins soutenue sur la classication et la sélection de variables dans le contexte de l'analyse de données et de la modélisation statistique (cf. Annexes A et A). Les travaux sur les mesures et intégrales non additives décrits dans ce document s'organisent selon deux axes : le premier axe porte sur l'interprétation de mesures non additives dans le contexte de la théorie des jeux coopératifs et de l'aide multicritère à la décision fondée sur les intégrales non additives ; le deuxième axe concerne l'identication de mesures non additives dans le contexte de l'agrégation par intégrale de Choquet. Ces deux directions de recherche sont fortement complémentaires dans la mesure où l'utilisation d'intégrales non additives dans un contexte décisionnel nécessite, dans un premier temps, l'identication d'une mesure non additive et, dans un deuxième temps, son interprétation an de rendre le modèle de décision plus transparent pour le décideur.

Les problèmes de robustesse liés à la substitution du calcul exact sur les réels par le calcul flottant approché sont souvent un obstacle à l'implantation pratique des algorithmes géométriques. Si l'adoption du paradigme exact apporte une solution satisfaisante à ce type de problèmes pour les algorithmes ayant un résultat purement combinatoire, cette solution ne permet cependant pas de résoudre en pratique le cas des algorithmes qui réutilisent voire cascadent la construction de nouveaux objets géométriques. Cette thèse aborde le problème de l'arrondi sur la grille entière du résultat d'opérations booléennes sur des régions polygonales et propose plusieurs notions d'arrondi permettant de garantir certaines propriétés métriques et topologiques intéressantes entre le résultat exact et sa version arrondie telles que la garantie de relations d'inclusion et la préservation de la convexité du résultat. Nos méthodes sont basées sur l'utilisation de constructeurs élémentaires arrondis pour lesquels nous présentons également plusieurs algorithmes efficaces. Nous proposons enfin des tests rapides permettant la détection robuste d'intersection entre plusieurs types d'objets convexes dans le plan et dans l'espace. L'ensemble de ces solutions trouvent une application directe en CAO et en graphisme.