The fabrication and characterization of surface-anchored hydrogel microstructures are described. The hydrogel structures are constructed from poly(N-isopropylacrylamide), or poly(NIPAAm), which is a well-known thermoresponsive polymer that swells and contracts with changes in temperature. When patterned on a surface, these structures can experience a variety of shape changes induced by nonuniform swelling. Depending on the aspect ratio, patterns can, for instance buckle upon swelling and form wave-like patterns. Such structural changes replicate oscillatory motion of the smooth muscle cells and can be used to transport objects in microfluidics. The work, herein, investigates methods of pattern production and introduces a new technique for characterizing local swelling in the patterns. In order to achieve the latter, fluorescent microspheres were embedded in hydrogel patterns and their positions were mapped in three-dimensions using confocal microscopy. The measurements permit, for the first time, swelling maps of the structures based on relative movements of the microspheres. This information will ultimately aid in understanding how swollen macroscopic structures are related to gradients in localized swelling.

Dans cette thèse, une approche pratique pour la génération de maillages triangulaires isotropes est proposée. En 2D comme en 3D, l'ob jectif consiste à mailler un domaine donné, pouvant avoir une géométrie complexe. L'approche présentée consiste à entrelacer des étapes de raffinement de Delaunay et des étapes d'optimisation de maillages dans le but de générer des maillages gradés de qualité. L'utilisateur peut contrôler les caractéristiques du maillage en définissant des critères de taille et de forme des simplexes, ainsi que de topologie et d'approximation. Les méthodes par éléments finis, largement utilisées en simulation, nécessitent des maillages gradés, composés de simplexes bien formés. Des alternatives aux méthodes de raffinement de Delaunay usuelles sont développées. Les méthodes d'optimisation de maillages proposées permettent d'optimiser la position des sommets intérieurs et de ceux du bord. Les caractéristiques du bord du domaine à mailler, et en particulier des arêtes vives, sont préservées par ces méthodes. En 2D, l'optimisation est basée sur l'algorithme de Lloyd et les diagrammes de Voronoi centrés (CVT). En 3D, une extension naturelle des triangulations de Delaunay optimales (ODT) de Chen, capable d'optimiser la position des sommets du bord du maillage, est introduite. Notre algorithme de maillage tétraédrique est enrichi par une étape de post-traitement permettant d'améliorer de façon significative la qualité des angles dièdres du maillage. Nous montrons que l'entrelacement d'étapes de raffinement et d'optimisation permet d'obtenir des maillages de meilleure qualité que ceux générés par les méthodes connues en termes d'angles dans les simplexes et de complexité.

Cette dernière décennie a vu apparaître et se développer toute une théorie sur l'échantillonnage des surfaces lisses. L'objectif était de trouver des conditions d'échantillonnage qui assurent une bonne reconstruction d'une surface lisse S à partir d'un sous-ensemble fini E de points de S. Parmi ces conditions, l'une des plus importantes est sans conteste la condition d'e-échantillonnage, introduite par Amenta et Bern, qui stipule que tout point p de S doit être à distance de E au plus e fois lfs(p), où lfs(p) désigne la distance de p à l'axe médian de S. Amenta et Bern ont montré qu'il est possible d'extraire de la triangulation de Delaunay d'un e-échantillon E une surface affine par morceaux qui approxime S du point de vue topologique (isotopie) et géométrique (distance de Hausdorff). Néanmoins restaient ouvertes les questions cruciales de pouvoir vérifier si un ensemble de points donné est un e-échantillon d'une part, et de construire des e-échantillons d'une surface lisse donnée d'autre part. De plus, les conditions d'échantillonnage proposées jusque là n'offraient des garanties que dans le cas lisse, puisque lfs s'annule aux points où la surface n'est pas différentiable. Dans cette thèse, nous introduisons le concept d'e-échantillon lâche, qui peut être vu comme une version faible de la notion d'e-échantillon. L'avantage majeur des e-échantillons lâches sur les e-échantillons classiques est qu'ils sont plus faciles à vérifier et à construire. Plus précisément, vérifier si un ensemble fini de points est un e-échantillon lâche revient à regarder si les rayons d'un nombre fini de boules sont suffisamment petits. Quand la surface S est lisse, nous montrons que les e-échantillons sont des e-échantillons lâches et réciproquement, à condition que e soit suffisamment petit. Il s'ensuit que les e-échantillons lâches offrent les mêmes garanties topologiques et géométriques que les e-échantillons. Nous étendons ensuite nos résultats au cas où la surface échantillonnée est non lisse en introduisant une nouvelle grandeur, appelée rayon Lipschitzien, qui joue un rôle similaire à lfs dans le cas lisse, mais qui s'avère être bien défini et positif sur une plus large classe d'objets. Plus précisément, il caractérise la classe des surfaces Lipschitziennes, qui inclut entre autres toutes les surfaces lisses par morceaux pour lesquelles la variation des normales aux abords des points singuliers n'est pas trop forte. Notre résultat principal est que, si S est une surface Lipschitzienne et E un ensemble fini de points de S tel que tout point de S est à distance de E au plus une fraction du rayon Lipschitzien de S, alors nous obtenons le même type de garanties que dans le cas lisse, à savoir : la triangulation de Delaunay de E restreinte à S est une variété isotope à S et à distance de Hausdorff O(e) de S, à condition que ses facettes ne soient pas trop aplaties. Nous étendons également ce résultat aux échantillons lâches. Enfin, nous donnons des bornes optimales sur la taille de ces échantillons. Afin de montrer l'intérêt pratique des échantillons lâches, nous présentons ensuite un algorithme très simple capable de construire des maillages certifiés de surfaces. Etant donné une surface S compacte, Lipschitzienne et sans bord, et un paramètre positif e, l'algorithme génère un e-échantillon lâche E de S de taille optimale, ainsi qu'un maillage triangulaire extrait de la triangulation de Delaunay de E. Grâce à nos résultats théoriques, nous pouvons garantir que ce maillage triangulaire est une bonne approximation de S, tant sur le plan topologique que géométrique, et ce sous des hypothèses raisonnables sur le paramètre d'entrée e. Un aspect remarquable de l'algorithme est que S n'a besoin d'être connue qu'à travers un oracle capable de détecter les points d'intersection de n'importe quel segment avec la surface. Ceci rend l'algorithme assez générique pour être utilisé dans de nombreux contextes pratiques et sur une large gamme de surfaces. Nous illustrons cette généricité à travers une série d'applications : maillage de surfaces implicites, remaillage de polyèdres, sondage de surfaces inconnues, maillage de volumes.

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.

Cette thèse propose de nouvelles méthodes pour accélérer certaines des plus importantes opérations dans une triangulation de Delaunay, conciliant efficacité et bonne complexité théorique. Nous proposons deux approches pour calculer la triangulation de Delaunay de points sur (ou proches) d'une sphère. La première approche calcule la triangulation de Delaunay de points exactement sur la sphère par construction. La deuxième approche calcule directement l'enveloppe convexe de l'ensemble d'entrée, et donne quelques garanties sur la sortie. Les deux approches sont basées sur la triangulation régulière sur la sphère. La deuxième approche améliore les solutions de l'état de l'art. L'operation de mise à jour d'une triangulation de Delaunay, quand les sommets bougent, est critique dans plusieurs domaines d'applications. Quand tous les sommets bougent, reconstruire toute la triangulation est étonnamment une bonne solution en pratique. Toutefois, lorsque les points se déplacent tres peu, ou si seulement une fraction des sommets bougent, la reconstruction n'est plus la meilleure option. Nous proposons un système de filtrage basé sur le concept de tolérance d'un sommet. Nous avons mené plusieurs expériences pour évaluer le comportement de l'algorithme sur des ensembles de données variés. Les expériences ont montré que l'algorithme est particulièrement pertinent pour les régimes convergents tels que les itérations de Lloyd. En dimension deux, l'algorithme présenté est un ordre de grandeur plus rapide que la reconstruction pour les itérations de Lloyd. En dimension trois, l'algorithme présenté a des performances équivalentes à la reconstruction quand tous les sommets bougent, cependant il est entièrement dynamique et améliore les solutions dynamiques précédentes. Ce résultat permet d'aller plus loin dans le nombre d'itérations de façon à produire des maillages de qualité supérieure. La localisation de points dans une subdivision de l'espace est un classique de la géométrie algorithmique; nous réexaminons ce problème dans le cas des triangulations de Rd pour exploiter une éventuelle cohérence entre les requêtes. Nous analysons, implementons, et évaluons une strategie de localisation de point adaptable aux distributions des requêtes, basée sur Jump & Walk, appellée Keep, Jump, &Walk. Pour des paquets de requêtes, l'idée principale est d'utiliser les requêtes précédentes pour améliorer le traitement de la requête courante. Maintenant à propos de la complexité d'une requête dans une triangulation de Delaunay, nous montrons que la hiérarchie de Delaunay peut être utilisée pour localiser un point q à partir d'une requête précédente p avec une complexité randomisée O(log ](pq)) pourvu que la triangulation vérifie certaines hypothèses (](s) désigne le nombre de simplex traversés par le segment s). Finalement, nous combinons la bonne adaptabilité à la distribution des requêtes du Keep, Jump, & Walk, et la bonne complexité de la hiérarchie de Delaunay, en une nouvelle stratégie de localisation de points appellée Keep, Jump, & Climb. Selon nos connaissances, Keep, Jump, & Climb est le premier algorithme adaptable aux distributions des requêtes qui marche en pratique et en théorie pour les triangulations de Delaunay--dans nos expérimentations, Keep, Jump, & Climb est plus rapide que la hiérarchie de Delaunay indépendamment de la cohérence spatiale des requêtes, et significativement plus rapide quand la cohérence spatiale est forte.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.

L'objet de cette thèse est la mise en place d'une boucle automatique pour le calcul de flux d'air conditionné dans des géométries complexes. Ce problème est régie par les équations de Navier-Stokes incompressible corrigées par un terme de Boussinesq et couplées avec une équation de température à flux convectif. <br />Nous avons utilisé une méthode d'adaptation de maillage anisotrope basée sur les longueurs d'arêtes avec respect d'une métrique discrète. Une méthode de remaillage local, avec une version anisotrope de l'insertion d'un point par une méthode de Delaunay, a été implémentée pour adapter les maillages.

In dieser Arbeit wird eine Erweiterung des Verfahrens von BOISSONAT vorgestellt, mit dem automatisch die Oberfläche eines 3-D-Objektes aus digitalisierten parallelen Schnittdaten rekonstrukiert werden kann. Dabei wird gewährleistet, dass die Oberfläche aus einer konsistenten und zulässigen Triangulierung besteht.

The methods presented in this study are aimed at the identification of subpopulations (clones) of genetically similar cells within tissue samples through measurement of loci-specific Fluorescence in-situ hybridization (FISH) spot signals for each nucleus and analyzing cell spatial distributions by way of Voronoi tessellation and Delaunay triangulation to robustly define cell neighbourhoods. The motivation for the system is to examine lung cancer patient for subpopulations of Non-Small Cell Lung Cancer (NSCLC) cells with biologically meaningful gene copy-number profiles: patterns of genetic alterations statistically associated with resistance to cis-platinum/vinorelbine doublet chemotherapy treatment. Current technologies for gene-copy number profiling rely on large amount of cellular material, which is not always available and suffers from limited sensitivity to only the most dominant clone in often heterogeneous samples. Thus, through the use of FISH, the detection of gene copy-numbers is possible in unprocessed tissues, allowing identification of specific tumour clones with biologically relevant patterns of genetic aberrations. The tissue-wide characterization of multiplexed loci-specific FISH signals, described herein, is achieved through a fully automated, multicolour fluorescence imaging microscope and object segmentation algorithms to identify cell nuclei and FISH spots within. Related tumour clones are identified through analysis of robustly defined cell neighbourhoods and cell-to-cell connections for regions of cells with homogenous and highly interconnected FISH spot signal characteristics. This study presents experiments which demonstrate the system’s ability to accurately quantify FISH spot signals in various tumour tissues and in up to 5 colours simultaneously or more through multiple rounds of FISH staining. Furthermore, the system’s FISH-based cell classification performance is evaluated at a sensitivity of 84% and specificity 81% and clonal identification algorithm results are determined to be comparable to clone delineation by a human-observer. Additionally, guidelines and procedures to perform anticipated, routine analysis experiments are established.