ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
Voronoï
Gueorgui Fedosievich,
russe, 1868-1908 |
Ce mathématicien russe étudia à l'université de Saint
Petersbourg (qui deviendra Leningrad après la révolution bolchévique de
1917). Il obtint son doctorat (1897) sous la direction de Andreï
A. Markov père, spécialiste en théorie des nombres à
qui l'on doit l'analyse markovienne (cryptage et codage des données).
Professeur à Varsovie, il meurt prématurément à l'âge de 40 ans. On lui doit des travaux en théorie des nombres et les diagrammes portant son nom, pavages irréguliers du plan et de surfaces dont le premier usage est attribué à Kepler.
Diagrammes de Voronoï :
Dans le plan euclidien, considérons un nuage N de points p1, p2, ..., pn appelés sites ou germes. Le diagramme de Voronoï associé à N correspond au pavage du plan caractérisé par la condition :
chaque pavé Ki est l'ensemble des points plus proches de pi que des autres points
» Ki ne contient donc aucun point de N autre que pi. Plutôt que de pavés, on parlera de cellules.
La médiatrice d'un segment [AB] partage le plan en deux demi-plans PA et PB tel que pour tout M de PA : AM ≤ BM et pour tout M de PB : BM ≤ AM. Cette propriété élémentaire permet le régionnement du plan correspondant au critère de Voronoï.
Ci-dessous, le cas de 2, 3 et 4 points :
a) Tracé des médiatrices permettant le régionnement de Voronoï :
b) Suppression des traces de construction (segments de médiatrices non pertinents) :
D'une façon générale, on peut gérer les points 3 par 3 en partant soit du "centre" approximatif du nuage de points donné, soit du point le plus "éloigné" de ce "centre". Ce principe de régionnement s'interprète comme des zones d'influence de chaque site du diagramme. Le procédé se généralise à l'espace (dimension 3).
Un bel exemple de diagramme de Voronoï : la girafe
réticulée de Somalie. Source
photo :
Snakes3yes (»
réf.8)
Historiquement, Descartes (1644, réf.7) utilisa de tels diagrammes en cosmologie afin de modéliser l'interaction gravitationnelle entre les étoiles, une quarantaine d'années avant la théorie newtonienne (1687) de la gravitation. Dans son modèle, deux sites (étoiles) sans frontière commune sont alors considérées indépendantes (absence d'interaction). Auparavant (1610), Kepler utilisa ce même procédé géométrique dans ses recherches d'optimisation de volumes et de surfaces.
Au milieu du 19è siècle, un médecin épidémiologue anglais, John Snow (1813-1858), utilisa ce type de diagramme afin de déterminer l'origine de l'épidémie de choléra qui toucha Londres : en construisant le diagramme des fontaines publiques et en dénombrant le nombre de malades dans chaque cellule, il put établir lesquelles étaient sans doute souillées.
Grâce aux ordinateurs, les diagrammes peuvent se construire aisément avec l'aide d'algorithmes adaptés à diverses situations : de nos jours, cet outil voit son application, ingénierie médicale (comme visualisation de l'évolution des cellules malades), en cristallographie (modélisation 3D), en navigation aérienne et maritime, en téléphonie mobile, dit à bon escient cellulaire, afin d'optimiser la connexion au relais le plus proche.
|
Triangulation de Delaunay (1934) : |
On connait le concept de triangulation géodésique permettant grâce à un "maillage" suffisamment fin d'une surface 3D, le calcul d'une distance ou d'une aire. La triangulation de Delaunay, étroitement liée aux diagrammes évoqués ci-dessus, voit aujourd'hui son application en imagerie numérique, du nom du mathématicien russe Boris Delone, un élève de Voronoï. L'algorithme se prête aisément à la programmation, en particulier pour l'ajout ou la suppression de certains points (» réf.5b, 5e).
i Boris Nikolaievich Delone (1890-1980), un élève de Voronoï, voit souvent son nom transformé en Delaunay car en russe Делоне (littéralement Delone) se lit Diélonié lorsqu'il n'est pas francisé. Il ne s'agit pas de Charles Eugène Delaunay, mais Boris Delone doit son nom à un ancètre français, officier de Napoléon capturé lors de la campagne de Russie (1812). Il publia d'ailleurs des articles en français sous son nom francisé (» réf.9). Professeur à Leningrad (Saint-Pétersbourg), algébriste, ses travaux portèrent sur la structure mathématique des cristaux et, par là, sur ce que l'on qualifie de géométrie des nombres (structures de réseaux de points du plan et de l'espace, ensemble de points à coordonnées entières, convexité).
Considérant un nuage N de points P1, P2, ..., Pn , la triangulation de Delaunay associée à N correspond à la triangulation de l'enveloppe convexe de ce dernier caractérisée par :
le cercle Ci,j,k circonscrit à chaque triangle PiPjPk ne contient aucun point de N en son intérieur
Remarques :
1. L'enveloppe convexe de N est le plus petit domaine convexe contenant tous les points de N. Dans ce cas "discret" d'un nombre fini de points, elle s'interprète comme le polygone convexe dont les sommets sont des points de N, tout autre point de N étant intérieur au polygone.
2. Une triangulation d'une surface convexe polygonale consiste à tracer un certain nombre de diagonales partageant ce polygone en un certain nombre de triangles, deux quelconques de ces diagonales ne pouvant s'intersecter :
Triangulation et géodésie : »
3. La frontière d'un domaine fermé ne fait pas partie de son intérieur : le cercle circonscrit à chaque triangle PiPjPk peut contenir un point (ou plus) du nuage N.
➔ Voici deux "essais" de triangulation de Delaunay relatives à l'hexagone ABCDEF. La première ne convient pas : les deux triangles EFB et EDB ont un angle obtus (> 90°) et dans un tel cas, le centre du cercle circonscrit se situe à l'extérieur du triangle, ce qui confère au cercle circonscrit un rayon important, donc la possibilité, comme on le constate, de contenir des points du nuage en son intérieur.
Comme on le voit ci-dessus, le critère de triangulation de Delaunay tend à maximiser, dans chaque triangle, la plus petite mesure de ses angles. Elle évite ainsi des triangle "aplatis" considérés, tout particulièrement en dimension 3, comme peu représentatifs de la surface, objet de la triangulation. Voici un diagramme de Voronoï plan (obtenu grâce au jeu indiqué en réf.1), limité à 25 sites et la triangulation de Delaunay qui lui est associée :
➔ En langage de la théorie des graphes, l'ensemble les frontières des cellules d'un diagramme de Voronoï (en bleu épais ci-dessus) s'interprète comme un graphe planaire G. Dans ce contexte, on remarquera que la triangulation de Delaunay associée (en vert fin) apparait comme le graphe dual G* de G.
Barak Obama, vu sur
Pinterst.com
➔ Pour en savoir plus :
Cartan
Élie