Practical ways to accelerate Delaunay triangulations

This thesis proposes several new practical ways to speed-up some of the most important operations in a Delaunay triangulation. We propose two approaches to compute a Delaunay triangulation for points on or close to a sphere. The first approach computes the Delaunay triangulation of points placed exactly on the sphere. The second approach directly computes the convex hull of the input set, and gives some guarantees on the output. Both approaches are based on the regular triangulation on the sphere. The second approach outperforms previous solutions. Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a viable option compared to relocating the vertices. However, when all points move with a small magnitude, or when only a fraction of the vertices moves, rebuilding is no longer the best option. We propose a filtering scheme based upon the concept of vertex tolerances. We conducted several experiments to showcase the behavior of the algorithm for a variety of data sets. The experiments showed that the algorithm is particularly relevant for convergent schemes such as the Lloyd iterations. In two dimensions, the algorithm presented performs up to an order of magnitude faster than rebuilding for Lloyd iterations. In three dimensions, although rebuilding the whole triangulation at each time stamp when all vertices move can be as fast as our algorithm, our solution is fully dynamic and outperforms previous dynamic solutions. This result makes it possible to go further on the number of iterations so as to produce higher quality meshes. Point location in spatial subdivision is one of the most studied problems in computational geometry. In the case of triangulations of R^d, we revisit the problem to exploit a possible coherence between the query points. We analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical Jump & Walk, called Keep, Jump, & Walk. For a batch of query points, the main idea is to use previous queries to improve the retrieval of the current one. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log #(pq)) randomized expected complexity, where p is a previously located query and #(s) indicates the number of simplices crossed by the line segment s. We combine the good distribution-sensitive behavior of Keep, Jump, & Walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called Keep, Jump, & Climb. To the best of our knowledge, Keep, Jump, & Climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations-in our experiments, it is faster than the Delaunay hierarchy regardless of the spatial coherence of queries, and significantly faster when queries have reasonable spatial coherence.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'opération 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 très peu, ou si seulement une fraction des sommets bouge, 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 R^d pour exploiter une éventuelle cohérence entre les requêtes. Nous analysons, implémentons, et évaluons une strategie de localisation de point adaptable aux distributions des requêtes, basée sur Jump & Walk, appel- lé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 independament de la cohérence spatiale des requêtes, et significativement plus rapide quand la cohérence spatiale est forte.NICE-BU Sciences (060882101) / SudocSudocFranceF