La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux " problèmes de placement de formes ", thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes.

Cette thèse s'intéresse aux constantes d'Hermite généralisées associées au groupe linéaire adèlique. A l'image de la théorie de Voronoï classique, on y définit deux propriétés, la perfection et l'eutaxie qui caractérisent les maxima locaux de l'invariant d'Hermite. Des inégalités et liens connus dans le cas classique sont étendus au cas général et fournissent la valeur de la constante dans certains cas. Par une théorie des designs définie pour la variété drapeau et semblable à celle des designs sphériques et grassmaniens, on fournit également de nombreux exemples d'objets atteignant l'extrémum. / This thesis studies generalised Hermite constants associated with the adelic general linear group. Like for the classical Voronoi theory, we define two properties, perfection and eutaxy, which characterise the local maxima of the Hermite invariant. Upper bounds and links known in the classical case are extended to the general case and provide the value of the constant in some cases. Through a theory of designs defined for the flag variety and similar to spherical or grassmanian design, we give also many examples of objects reaching locally the extremum.

Cet ouvrage aborde la génération de grilles de Voronoï sous contrainte pour réduire les erreurs liées à la géométrie des cellules lors de la simulation réservoir. Les points de Voronoï sont optimisés en minimisant des fonctions objectif correspondant à différentes contraintes géométriques. L'originalité de cette approche est de pouvoir combiner les contraintes simultanément : - la qualité des cellules, en plaçant les points de Voronoï aux barycentres des cellules ; - le raffinement local, en fonction d'un champ de densité [rho], correspondant à la perméabilité, la vitesse ou la vorticité ; - l'anisotropie des cellules, en fonction d'un champ de matrice M contenant les trois vecteurs principaux de l'anisotropie, dont l'un est défini par le vecteur vitesse ou par le gradient stratigraphique ; - l'orientation des faces des cellules, en fonction d'un champ de matrice M contenant les trois vecteurs orthogonaux aux faces, dont l'un est défini par le vecteur vitesse ; - la conformité aux surfaces du modèle structural, failles et horizons ; - l'alignement des points de Voronoï le long des puits. La qualité des grilles générées est appréciée à partir de critères géométriques et de résultats de simulation comparés à des grilles fines de référence. Les résultats indiquent une amélioration de la géométrie, qui n'est pas systématiquement suivie d'une amélioration des résultats de simulation / Voronoi grids are generated under constraints to reduce the errors due to cells geometry during flow simulation in reservoirs. The Voronoi points are optimized by minimizing objective functions relevant to various geometrical constraints. An original feature of this approach is to combine simultaneously the constraints: - Cell quality, by placing the Voronoi points at the cell barycenters. - Local refinement according to a density field rho, relevant to permeability, velocity or vorticity. - Cell anisotropy according to a matrix field M built with the three principal vectors of the anisotropy, which one is defined by the velocity vector or by the stratigraphic gradient. - Faces orientation according to a matrix field M built with the three vectors orthogonal to the faces, which one is defined by the velocity vector. - Conformity to structural features, faults and horizons. - Voronoï points alignment along well path. The quality of the generated grids is assessed from geometrical criteria and from comparisons of flow simulation results with reference fine grids. Results show geometrical improvements, that are not necessarily followed by flow simulation results improvements

Notre travail concerne l'étude, le calcul et la simplification des squelettes d'objets 2D et 3D. Le squelette d'un objet est une figure mince, centrée dans la forme et qui en résume l'aspect. Il est utile pour la description et la reconnaissance de formes, la quantification, la mise en correspondance, etc. Dans un premier temps, nous recensons les différentes techniques de calcul du squelette. La très grande majorité d'entre elles travaille sur des images binaires avec des outils de la géométrie discrète. Or, dernièrement, une nouvelle famille de méthodes, appelées méthodes continues a vu le jour. Le squelette est approché à l'aide du graphe de Voronoï d'un échantillonnage de la frontière, et se calcule par des moyens propres à la géométrie algorithmique. Notre intérêt s'est porté sur cette nouvelle approche et les problèmes qui s'y rattache. Pour commencer, nous proposons une formulation des méthodes continues à l'aide du squelette d'une union finie de sphères. En effet, nous montrons que le squelette d'une union finie de sphères se construit de façon exacte à l'aide d'éléments très simples comme des segments de droite en 2D et des polygones en 3D. La construction du squelette nécessite de pouvoir interpoler par des facettes triangulaires un ensemble de points localisés sur la frontière d'un objet. Nous proposons une méthode, fondée sur le calcul du graphe de Delaunay et dont nous montrons la convergence en 2D. Enfin, des méthodes de simplification du squelette sont présentées. Elles permettent de sélectionner les branches correspondant à des renflements significatifs de la forme et conduisent en 3D soit à des squelettes surfaciques, soit à des squelettes filiformes selon les besoins de l'utilisateur. Pour finir, nous décrivons une application qui valide notre approche, et l'illustre sur des données biologiques

Ce travail porte sur la mise en oeuvre en 3d de la méthode des éléments naturels contrainte CNEM en vue de son utilisation pour la simulation du cisaillage à grande vitesse. La CNEM est une approche à mi-chemin des approches sans maillage et des éléments finis. La construction de son interpolation utilise le diagramme de Voronoï contraint (dual du maillage de Delaunay contraint) associé à un nuage de noeud réparti sur le domaine étudié muni d'une description de sa frontière. La mise en oeuvre de la CNEM comporte trois aspects principaux : i) la construction du diagramme de Voronoï contraint, ii) le calcul des fonctions de forme éléments naturels Sibson, iii) la discrétisation d'une formulation variationnelle générique par utilisation de l'intégration nodale stabilisée conforme, SCNI, introduite par Chen et Al en 2001. Une partie importante de ce travail concerne les deux derniers points. Pour le calcul des fonctions de formes Sibson 3d cinq algorithmes sont présentés, dont deux développés au cours de la thèse, et sont comparés en terme de performance. Par ailleurs, une discrétisation est proposée pour être applicable au cas des domaines fortement non convexes. La mise en oeuvre proposée est validée sur des exemples en élasticité linéaire 3d en petites perturbations (vis à vis de solutions analytiques et de résultats éléments finis) puis en grandes transformations (test de la barre de Taylor). L'application de la CNEM au cisaillage grande vitesse est finalement abordée. Les développements effectués ont été intégrés à la plateforme logicielle Nessy. Cette plateforme a pour objectif la capitalisation du savoir faire du LMSP en simulation numérique.

Dans de nombreux domaines d'applications, une variété plongée dans l'espace euclidien est souvent représentée par un échantillon de points. Nous définissons dans cette thèse un système de coordonnées associé à un tel échantillon sur la variété qui généralise les coordonnées naturelles définies par Sibson. Nous exhibons ses propriétés mathématiques fondamentales ainsi que son application à l'interpolation d'une fonction définie sur la variété. Nous introduisons la notion d'atlas de Voronoï, défini comme un ensemble de cellules approximant le diagramme de Voronoï restreint à la variété et montrons son application à la reconstruction de surface et au remaillage. Enfin, nous étendons les propriétés des coordonnées naturelles aux diagrammes de puissance et proposons une synthèse des méthodes d'interpolation par coordonnées naturelles. Cette dernière détaille des preuves omises dans les articles originaux.

Les fonctions de la majorité des protéines sont subordonnées à l'interaction avec un ou plusieurs partenaires : acides nucléiques, autres protéines... La plupart de ces interactions sont transitoires, difficiles à détecter expérimentalement et leurs structures sont souvent impossible à obtenir. C'est pourquoi la prédiction in silico de l'existence de ces interactions et la structure du complexe résultant ont été l'objet de nombreuses études depuis plus d'une décennie maintenant. Pour autant les protéines sont des objets complexes et les méthodes informatiques classiques sont trop "gourmandes" en temps pour l'exploration à grande échelle de l'interactome des différents organismes. Dans ce contexte de développement d'une méthode de docking protéine-protéine haut débit nous présenterons ici l'implémentation d'une nouvelle méthode d'amarrage, celle-ci est basée sur : l'utilisation de deux types de formalismes : Les tessellations de Voronoï et Laguerre permettant la manipulation de modèles géométriques simplifiés permettant une bonne modélisation des complexes et des temps de calcul plus raisonnable qu'en représentation atomique. L'utilisation et l'optimisation d'algorithmes d'apprentissage (algorithmes génétiques) permettant d'isoler les conformations les plus pertinentes entre deux partenaires protéiques. Une méthode d'évaluation basée sur le clustering de méta-attributs calculés au niveau de l'interface permettant de trier au mieux ce sous-ensemble de conformations candidates.

Les bouleversements architecturaux induits dans la muqueuse colique par la cancérisation ont été étudiés par une approche morphologique sur des cancers colorectaux sporadiques comparés à des échantillons coliques non cancéreux. En premier lieu, la muqueuse normale au contact du cancer a été individualisée de la muqueuse normale à distance par ses caractéristiques histo-morphométriques, qui montrent son épaississement tandis que sa densité en cryptes est significativement diminuée ; son profil prolifératif, mis en évidence par le marquage aux anticorps Ki-67, β-caténine et Cycline D1, reste analogue à celui de la muqueuse à distance. Ceci suggère un mécanisme de conservation de l'équilibre cellulaire des cryptes au contact de l'expansion tumorale. Dans un deuxième temps, l'individualisation des cellules prolifératives au moyen des anticorps déjà cités a permis d'étudier les modifications de distribution de ces cellules dans les cancers, ainsi que le désordre qui en résulte. A cette fin, l'utilisation du diagramme de Voronoï, outil de sociologie cellulaire, a montré un réarrangement dans l'espace des cellules cancéreuses qui est discriminant par rapport à la muqueuse normale adjacente, et qui est le fait uniquement des cellules Ki-67 positives. En dernier lieu l'accent a été mis sur l'hétérogénéité du marquage des cellules tumorales. Cette hétérogénéité a été étudiée de façon semi-quantitatives sur des zones de " spots virtuels ", puis de façon quantitative au moyen de l'index d'hétérogénéité spatiale, outil mathématique lié aux statistiques spatiales. L'hétérogénéité du marquage est importante dans les dysplasies, et tend à s'atténuer dans les tumeurs les plus évoluées.

Nous nous intéressons au problème de la reconstruction tridimensionnelle d'objets complexes à partir de coupes sériées. Le premier chapitre du mémoire s'attache à montrer l'intérêt de mettre à la disposition de la modélisation géologique 3D un ensemble d'outils variés et notamment des méthodes d'interpolation et de reconstruction adaptées. Le second chapitre pose la problématique générale de la reconstruction 3D et propose un état de l'art sur les méthodes existantes. Ces deux chapitres composent la première partie du manuscrit. Dans la deuxième partie du mémoire nous proposons une nouvelle méthode de reconstruction 3D qui permet de traiter de manière simple et automatique l'ensemble des problèmes de topologie (trous, branchements multiples, contours isolés). Elle s'appuie sur la construction adaptative de coupes intermédiaires par interpolation entre les sections initiales (chapitre 3). Ce processus utilise un diagramme de Voronoï généralisé simplifié, le réseau bissecteur, comme outil d'interpolation 2D. Nous fournissons une description géométrique complète du réseau bissecteur 2D et nous montrons que sa complexité algébrique est la même que celle des éléments qui permettent de le calculer (segments en 2D, portions de plans en 3D). Nous proposons ensuite deux algorithmes de construction des réseaux bissecteurs interne et externe de formes polygonales éventuellement trouées, dont la complexité en temps est respectivement en O(n2 log n) et O(n2), et la mémoire en O(n2) et O(n) respectivement (chapitre 4). La mise en correspondance des contours est abordée dans le chapitre 5 et nous suggérons quelques solutions pour traiter certains problèmes délicats. La construction du réseau bissecteur permet ensuite d'obte~ir une surface valide de l'objet en guidant de manière directe la triangulation entre les points des différentes sections. Il n'y a donc pas besoin de post-traitements. De plus, l'ajout automatique de portions de coupes intermédiaires dans les zones de changements de topologie ou de variations de morphologie permet une meilleure définition des surfaces générées (chapitre 6). Dans la dernière partie du mémoire nous discutons les résultats obtenus et nous les comparons avec ceux de deux méthodes existantes (chapitre 7).