Expected Size of the 3-Dimensional Delaunay Triangulation of Random Points on a Surface - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2022

Expected Size of the 3-Dimensional Delaunay Triangulation of Random Points on a Surface

Taille moyenne de la triangulation 3D de Delaunay de points aléatoirement distribués sur une surface

Résumé

This thesis aims at evaluating the size of the Delaunay triangulation of points drawn on a surface with a random distribution. The Delaunay triangulation, is a geometrical object that appeared recurrently in the scientific history. In dimension 2, the Delaunay triangulation is the set of triangles for which the circumscribing circle does not contain other points of X. This definition is generalizable in higher dimensions. Today, the Delaunay triangulation is one the most studied structures in computational geometry. For the 2 dimensional case, we know that the size of the Delaunay triangulation remains linear with the number of points. In 3 dimension, it is not anymore the case. The size of the 3D-Delaunay triangulation can range from linear to quadratic. This size depends on how the points are distributed in R^3. On a surface, the size of the Delaunay triangulation will depend both on the surface and on how they are distributed on this surface. To model points, we choose to use a Poisson point process since it verifies properties of homogeneity and independence that are convenient for the computations. In order to prove the expected O(n log n) bound for the uniform sample distributed on a cylinder, Devillers et al. remarked that the intersection of the cylinder with a sphere passing though two points p and q on the cylinder always contains a specific triangle drawn on the cylinder. That leads them to study a 2-dimensional graph in which two points are neighbors if there exists such a triangle that does not contain other data points. Such a graph has expected size O(n log n), and this is how they obtain the O(n log n) bound. In Part II, we define a kind of empty region graphs, we formalize a method to compute lower and upper bounds on their expected size, and give tight results for such graphs. As Attali et al. pointed out, the intersection of a sphere with a generic surface has almost an elliptic shape, aligned with the curvature directions of the surface. This leads us to study a particular empty region graph for which the regions are axis-aligned ellipses. We prove, in Part II, that if the involved ellipses have an aspect ratio ranging from b to 1, with 0 < b < 1, then the expected number of neighbors of any point in the graph is O(ln b). In order to illustrate the method, we compute, in Part III, tight asymptotic bounds on the expected size of the 3D-Delaunay triangulation in two specific cases. In Part III, Chapter 12, we consider a cylinder of revolution and reprove the O(N ln N) bound but for a Poisson point process. Considering the similarity between uniform and Poisson sample, the goal of this chapter is mainly to present concretely the method in a 3-dimensional simple case. Then, in Chapter 13, we compute the size of the 3D-Delaunay triangulation of a Poisson process distributed on a flattened sphere. We show that the expected size of the triangulation is O(N). Finally in Part IV, we treat the case of generic surfaces. Even if an oblate spheroid is a specific surface, we will be able to reuse some computations in this part up to some adaptations. Indeed the oblate spheroid is the surface of a convex body, that is not generally the case. It has a lot of symmetries, that is not generally the case either. In this part, we focus more on how to deal with these adaptations than on the computations that were already quite tedious in the spheroid case.
Cette thèse a pour but d' évaluer la taille de la triangulation de Delaunay de points distribués sur une surface avec une distribution aléatoire. La triangulation de Delaunay, est un objet géométrique qui est apparu de manière récurrente dans l'histoire scientifique. En dimension 2, la triangulation de Delaunay de X est l'ensemble des triangles pour lesquels le cercle circonscrit ne contient pas d'autres points de X. Cette définition est généralisable en dimension supérieure. Aujourd'hui, la triangulation de Delaunay est l'une des structures les plus étudiées en géométrie algorithmique. Pour le cas en 2 dimensions, on sait que la taille de la triangulation de Delaunay reste linéaire avec le nombre de points. En 3 dimensions, la taille de la triangulation de Delaunay peut varier de linéaire à quadratique. Cette taille dépend de la façon dont les points sont distribués dans R^3. Sur une surface, la taille de la triangulation de Delaunay dépendra à la fois de la surface et de la façon dont ils sont répartis sur cette surface. Pour modéliser les points, nous choisissons d'utiliser un processus ponctuel de Poisson car il vérifie des propriétés d'homogénéité et d'indépendance qui sont pratiques pour les calculs. Afin de prouver la borne O(n log n) en espérance pour l'échantillon uniforme distribué sur un cylindre, Devillers et al. ont remarqué que l'intersection du cylindre avec une sphère passant par deux points p et q sur le cylindre contient toujours un triangle spécifique dessiné sur le cylindre. Cela les conduit à étudier un graphe à 2 dimensions dans lequel deux points sont voisins s'il existe un tel triangle qui ne contient pas d'autres points de données. Un tel graphe a une taille moyenne de O(n log n), et c'est ainsi qu'ils obtiennent la borne O(n log n). Dans la partie II, nous définissons un type de graphes de régions vides, nous formalisons une méthode pour calculer les limites inférieures et supérieures de leur taille moyenne, et nous donnons des résultats optimaux pour ces graphes. Comme Attali et al. l'ont souligné, l'intersection d'une sphère avec une surface générique a presque une forme elliptique, alignée avec les directions de courbure de la surface. Ceci nous amène à étudier un graphe particulier de régions vides pour lequel les régions sont des ellipses alignées avec les axes. Nous prouvons, dans la partie II, que si les ellipses concernées ont un rapport d'aspect compris entre b et 1, avec 0 < b < 1, alors le nombre moyen de voisins de tout point du graphe est O(ln b). Afin d'illustrer la méthode, nous calculons, dans la partie III, les limites asymptotiques sur la taille moyenne de la triangulation 3D-Delaunay dans deux cas spécifiques. Dans la partie III, chapitre 12, nous considérons un cylindre de révolution et confirmons la limite O(n ln n) mais pour un processus ponctuel de Poisson. Compte tenu de la similitude entre l'échantillon uniforme et l'échantillon de Poisson, le but de ce chapitre est principalement de présenter concrètement la méthode dans un cas simple en 3 dimensions. Ensuite, dans le chapitre 13, nous calculons la taille de la triangulation 3D-Delaunay d'un processus de Poisson distribué sur une sphère aplatie. Nous montrons que la taille moyenne de la triangulation est O(n). Enfin, dans la partie IV, nous traitons le cas des surfaces génériques. Même si un sphéroïde aplati est une surface spécifique, nous pourrons réutiliser certains calculs de cette partie moyennant quelques adaptations. En effet, le sphéroïde aplati est la surface d'un corps convexe, ce qui n'est généralement pas le cas en général. Dans cette partie, nous nous concentrons plus sur la façon de gérer ces adaptations que sur les calculs qui étaient déjà assez fastidieux dans le cas du sphéroïde.
Fichier principal
Vignette du fichier
TheseCharlesDumenilVersionFinale.pdf (9.75 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-03695908 , version 1 (15-06-2022)

Identifiants

  • HAL Id : tel-03695908 , version 1

Citer

Charles Duménil. Expected Size of the 3-Dimensional Delaunay Triangulation of Random Points on a Surface. Computational Geometry [cs.CG]. Université de Lorraine, 2022. English. ⟨NNT : 2022LORR0050⟩. ⟨tel-03695908⟩
194 Consultations
113 Téléchargements

Partager

Gmail Facebook X LinkedIn More