sujets d’étude de la géométrie algorithmique,
et c’est dans les années 1980 que l’on a établi
leur lien avec la théorie des polytopes (analogues des polyèdres dans les espaces de
dimension supérieure à trois). Leur étude dans
le contexte de l’échantillonnage des surfaces
est beaucoup plus récente.
Quel est l’intérêt des diagrammes de
Voronoï et des triangulations de Delaunay ?
Si E est un échantillon de n points pris sur une
surface S, on peut montrer que son diagramme
de Voronoï et la triangulation de Delaunay
correspondante contiennent beaucoup d’informations sur cette surface. Lorsque l’échantillonnage est suffisamment dense, on peut
fournir des approximations précises de la surface. Par exemple, le vecteur qui joint un point
P de E au sommet le plus éloigné de sa cellule
de Voronoï est une bonne approximation de
la normale à la surface S au point P.
Il faut s’assurer que les temps de
calcul resteront raisonnables, que les
algorithmes sont fiables
C’est ainsi que l’on connaît aujourd’hui
plusieurs algorithmes de reconstruction
capables, à partir d’un échantillon fini de points
d’une surface S, de construire une surface S’
qui approxime correctement la surface réelle
S. Qui plus est, la théorie de ces algorithmes
permet de calculer une borne supérieure sur
la différence entre S’ et S, borne qui dépend
évidemment de la densité d’échantillonnage.
Comme les jeux de données fournis par les
instruments de mesure comportent généralement plusieurs centaines de milliers de points,
voire des millions, les questions combinatoires
et algorithmiques jouent un rôle critique. Il est
par exemple important de savoir si la quantité
de calculs que nécessite la triangulation de
Delaunay restera ou non dans une limite raisonnable. Dans les cas les plus défavorables, le
nombre T d’étapes de calcul (c’est-à-dire, en fin
de compte, le temps de calcul) peut être quadratique ; autrement dit, T est au pire proportionnel au carré du nombre de points de l’échantillonnage. On suppose toutefois que cette
situation ne se produit pas dans le cas de surfaces bien échantillonnées. Des résultats plus
précis ont été démontrés très récemment dans
le cas de surfaces S polyédriques, c’est-à-dire
constituées uniquement de facettes polygonales: pour de telles surfaces et pour des conditions d’échantillonnage faibles, la taille du calcul de triangulation est, au pire, proportionnelle
au nombre de points échantillonnés. Le cas des
surfaces lisses est plus délicat ; il fait actuellement l’objet de recherches actives.
Les bornes théoriques ne sont pas tout,
reste à savoir calculer effectivement et rapidement la triangulation d’un jeu de données.
On connaît de nombreux algorithmes. Les plus
efficaces sont dits randomisés car ils effectuent
certains tirages aléatoires au cours de leur
déroulement. La théorie des algorithmes randomisés s’est développée très rapidement dans
90
L’explosion des mathématiques
Figure 3. Le diagramme de Voronoï d’un ensemble de points pris sur
une courbe.
et c’est dans les années 1980 que l’on a établi
leur lien avec la théorie des polytopes (analogues des polyèdres dans les espaces de
dimension supérieure à trois). Leur étude dans
le contexte de l’échantillonnage des surfaces
est beaucoup plus récente.
Quel est l’intérêt des diagrammes de
Voronoï et des triangulations de Delaunay ?
Si E est un échantillon de n points pris sur une
surface S, on peut montrer que son diagramme
de Voronoï et la triangulation de Delaunay
correspondante contiennent beaucoup d’informations sur cette surface. Lorsque l’échantillonnage est suffisamment dense, on peut
fournir des approximations précises de la surface. Par exemple, le vecteur qui joint un point
P de E au sommet le plus éloigné de sa cellule
de Voronoï est une bonne approximation de
la normale à la surface S au point P.
Il faut s’assurer que les temps de
calcul resteront raisonnables, que les
algorithmes sont fiables
C’est ainsi que l’on connaît aujourd’hui
plusieurs algorithmes de reconstruction
capables, à partir d’un échantillon fini de points
d’une surface S, de construire une surface S’
qui approxime correctement la surface réelle
S. Qui plus est, la théorie de ces algorithmes
permet de calculer une borne supérieure sur
la différence entre S’ et S, borne qui dépend
évidemment de la densité d’échantillonnage.
Comme les jeux de données fournis par les
instruments de mesure comportent généralement plusieurs centaines de milliers de points,
voire des millions, les questions combinatoires
et algorithmiques jouent un rôle critique. Il est
par exemple important de savoir si la quantité
de calculs que nécessite la triangulation de
Delaunay restera ou non dans une limite raisonnable. Dans les cas les plus défavorables, le
nombre T d’étapes de calcul (c’est-à-dire, en fin
de compte, le temps de calcul) peut être quadratique ; autrement dit, T est au pire proportionnel au carré du nombre de points de l’échantillonnage. On suppose toutefois que cette
situation ne se produit pas dans le cas de surfaces bien échantillonnées. Des résultats plus
précis ont été démontrés très récemment dans
le cas de surfaces S polyédriques, c’est-à-dire
constituées uniquement de facettes polygonales: pour de telles surfaces et pour des conditions d’échantillonnage faibles, la taille du calcul de triangulation est, au pire, proportionnelle
au nombre de points échantillonnés. Le cas des
surfaces lisses est plus délicat ; il fait actuellement l’objet de recherches actives.
Les bornes théoriques ne sont pas tout,
reste à savoir calculer effectivement et rapidement la triangulation d’un jeu de données.
On connaît de nombreux algorithmes. Les plus
efficaces sont dits randomisés car ils effectuent
certains tirages aléatoires au cours de leur
déroulement. La théorie des algorithmes randomisés s’est développée très rapidement dans
90
L’explosion des mathématiques
Figure 3. Le diagramme de Voronoï d’un ensemble de points pris sur
une courbe.