Certains voient en les mathématiciens grecs des MM. Jourdain de la géométrie algorithmique, mais celle-ci n’a vraiment pris son essor qu’à partir des années 1970, avec l’arrivée de la conception assistée par ordinateur (CAO). Il s’agit alors souvent de fournir des représentations numériques de formes tridimensionnelles. Beaucoup de nouvelles questions se posent rapidement, y compris pour de la « simple » géométrie plane. Il est notamment essentiel de gérer au mieux la complexité des représentations. Pour cela, les mathématiques apportent des outils offrant une portée universelle en étudiant notamment différents maillages des surfaces, différentes triangulations, afin de répondre au mieux aux questions délicates concernant le passage du continu au discret. Passons en revue quelques questions emblématiques de ce domaine passionnant et très actif de la recherche mathématique.
Les plus proches voisins ------------------------
Donnez-vous un ensemble fini de points du plan. Comment trouver « rapidement » les deux points qui sont les plus proches l’un de l’autre ? Quand le nombre de points n’est pas très élevé, on peut répondre à la question intuitivement et sans grand risque d’erreur. Lorsque le nombre de points augmente, une approche plus organisée s’impose. On peut, de façon assez naïve et brutale, calculer toutes les longueurs en jeu. Pour n points, cela donne n(n – 1)/2 calculs et globalement, on dit que la complexité en temps de cette méthode est de l’ordre de n 2.
On peut procéder autrement avec une approche récursive subtile. On partage l’ensemble des points en deux parties comptant le même nombre de points (ou presque si ce nombre est impair) séparées par une droite verticale et on résout le problème récursivement pour ces deux parties. Il reste ensuite à combiner les résultats obtenus pour ces deux ensembles. Quelques astuces permettent de limiter les calculs à cette étape de combinaison (voir encadré). La complexité en temps de cette méthode est de l’ordre n log(n), un gain loin d’être anecdotique quand le nombre de points devient très grand !
La méthode peut se généraliser à l’espace à trois dimensions (ou plus) et offre alors des applications concrètes dans bien des domaines, comme le contrôle aérien.