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.

Cette thèse est une contribution à un problème classique de la géométrie algorithmique et combinatoire : l’étude des k-sets d’un ensemble V de n points du plan. Nous introduisons d’abord la notion de chaîne d’inclusion de convexes qui est un ordonnancement des points de V tel qu’aucun point n’appartient à l’enveloppe convexe de ceux qui le précèdent. Tout k-set d’une sous-suite commençante de la chaîne est appelé un k-set de la chaîne. Nous montrons que le nombre de ces k-sets est un invariant de V et qu’il est égal au nombre de régions du diagramme de Voronoï d’ordre k de V. Nous en déduisons un algorithme en ligne pour construire les k-sets des sommets d’une ligne polygonale simple dont chaque sommet est à l’extérieur de l’enveloppe convexe des sommets qui le précèdent sur la ligne. Si c est le nombre total de k-sets construits, la complexité de notrealgorithme est en O(n log n+c log^2 k) et est équivalente, par k-set construit, à celle du meilleur algorithme connu. Nous montrons ensuite que la méthode algorithmique classique de division-fusion peut être adaptée à la construction des k-sets de V. L’algorithme qui en résulte a une complexité enO(n log n+c log^2 k log(n/k)), où c est le nombre maximum de k-sets d’un ensemble de n points.Nous prouvons enfin que les centres de gravité des k-sets d’une chaîne d’inclusion de convexes sont les sommets d’une triangulation qui appartient à la même famille de triangulations, dites centroïdes, que le dual du diagramme de Voronoï d’ordre k. Nous en d´déduisons un algorithme qui construit des triangulations centroïdes particulières en temps O(n log n+k(n-k) log^2 k), ce qui est plus efficace que les algorithmes connus jusque là. / This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

Parmi les méthodes de super-résolution, la microscopie par localisation de molécules uniques se distingue principalement par sa meilleure résolution réalisable en pratique mais aussi pour l’accès direct aux propriétés des molécules individuelles. Les données principales de la microscopie par localisation sont les coordonnées des fluorochromes, un type de données peu répandu en microscopie conventionnelle. Le développement de méthodes spéciales pour le traitement de ces données est donc nécessaire. J’ai développé les logiciels SharpViSu et ClusterViSu qui permettent d’effectuer les étapes de traitements les plus importantes, notamment une correction des dérives et des aberrations chromatiques, une sélection des événements de localisations, une reconstruction des données dans des images 2D ou dans des volumes 3D par le moyen de différentes techniques de visualisation, une estimation de la résolution à l’aide de la corrélation des anneaux de Fourier, et une segmentation à l’aide de fonctions K et L de Ripley. En plus, j’ai développé une méthode de segmentation de données de localisation en 2D et en 3D basée sur les diagrammes de Voronoï qui permet un clustering de manière automatique grâce à modélisation de bruit par les simulations Monte-Carlo. En utilisant les méthodes avancées de traitement de données, j’ai mis en évidence un clustering de la protéine CENP-A dans les régions centromériques des noyaux cellulaires et des transitions structurales de ces clusters au moment de la déposition de la CENP-A au début de la phase G1 du cycle cellulaire. / Among the super-resolution methods single-molecule localization microscopy (SMLM) is remarkable not only for best practically achievable resolution but also for the direct access to properties of individual molecules. The primary data of SMLM are the coordinates of individual fluorophores, which is a relatively rare data type in fluorescence microscopy. Therefore, specially adapted methods for processing of these data have to be developed. I developed the software SharpViSu and ClusterViSu that allow for most important data processing steps, namely for correction of drift and chromatic aberrations, selection of localization events, reconstruction of data in 2D images or 3D volumes using different visualization techniques, estimation of resolution with Fourier ring correlation, and segmentation using K- and L-Ripley functions. Additionally, I developed a method for segmentation of 2D and 3D localization data based on Voronoi diagrams, which allows for automatic and unambiguous cluster analysis thanks to noise modeling with Monte-Carlo simulations. Using advanced data processing methods, I demonstrated clustering of CENP-A in the centromeric regions of the cell nucleus and structural transitions of these clusters upon the CENP-A deposition in early G1 phase of the cell cycle.