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 ...
Lire la suite