Cette thèse de 1978 a fait naître un domaine : la géométrie algorithmique. L’auteur a étudié attentivement la géométrie et l’algorithmique, et sa thèse est remplie de questions d’entretiens^W^W méthodes encore utilisées aujourd’hui pour un bon nombre de problème géométriques :
- test de convexité ;
- enveloppe convexe ;
- diamètre d’un polygone ;
- intersections ;
- plus proches voisins ;
- diagrammes de Voronoï.
Pour ne citer qu’un domaine d’application, le jeu vidéo utilise énormément les intersections et les plus proches voisins.
L’algorithme utilisé pour déterminer le diamètre d’un polygone (la distance maximum entre deux points) est assez élégant et mérite d’être connu. Il s’exécute en O(n) une fois qu’on a l’enveloppe convexe (qui peut aussi se faire en O(n) suivant les préconditions). On l’appelle l’algorithme des "rotating calipers" (littéralement pieds à coulisse rotatifs) et il a ensuite été généralisé à une myriade d'autres problèmes.
Lire maintenant ?