Loading AI tools
problème qui consiste à trouver une paire de points d'un ensemble fini de points dans un espace métrique dont la distance est minimale De Wikipédia, l'encyclopédie libre
En géométrie algorithmique, la recherche des deux points les plus rapprochés est le problème qui consiste à trouver une paire de points d'un ensemble fini de points dans un espace métrique dont la distance est minimale. Il fait partie des problèmes fondateurs de la géométrie algorithmique[1].
En notant le nombre de points, l'algorithme naïf par recherche exhaustive a une complexité en temps en . Il y a en effet paires différentes à tester.
Il existe un algorithme basé sur diviser pour régner en [2].
L'algorithme se déroule en plusieurs étapes[3]:
La résolution des deux sous-problèmes permet de déterminer que si la paire de points les plus proches a une extrémité de chaque côté de la droite de partition, alors la distance qui les sépare est inférieure à . Il suffit donc de s'intéresser à la bande verticale de largeur centrée en la droite de partition. On procède comme suit[3]:
La terminaison de l'algorithme est assurée par le fait que l'on a choisi pour limite de récursivité , ce qui assure qu'aucun appel récursif n'est lancé sur un seul point[3].
Le point le plus important à vérifier pour établir la correction de l'algorithme est le fait que dans l'étape de combinaison des résultats des sous-problèmes, il suffit de calculer la distance entre chaque point et les sept suivants dans pour trouver une éventuelle paire de points séparés d'une distance inférieure à [3]. On suppose qu'il existe pour l'un des sous-problèmes récursifs une paire de points et séparés d'une distance inférieure à (où est le minimum des distances trouvées dans et séparément). et sont tous deux compris dans un même rectangle centré sur la droite de partition, de longueur et de hauteur .
On cherche à savoir combien de points au maximum peuvent se trouver dans ce rectangle, sachant que deux points situés du même côté de la droite de partition sont distants d'au moins . La réponse est 8 : un à chaque coin, et un couple de points superposés situé à chacun des milieux des grands côtés du rectangle[3]. Cet argument repose sur l'intuition géométrique et n'est pas adapté à une formalisation rigoureuse, mais peut être remplacé par une utilisation du principe des tiroirs qui donne la même borne de manière rigoureuse[4]. Par conséquent au plus 7 autres points de la bande ont une ordonnée supérieure de moins de à l'ordonnée du point . On peut donc trouver en calculant au plus 7 distances depuis . On peut donc trouver une paire minimale si elle existe au sein de la bande en calculant pour chacun de ses points les distances qui le séparent des 7 points qui le suivent dans [3].
La validité du reste de l'algorithme ne nécessite pas de preuve détaillée[3], celle-ci a néanmoins été vérifiée formellement dans son intégralité à l'aide de l'assistant de preuve Isabelle[4].
On commence par regarder la complexité des différentes étapes de l'algorithme :
La complexité de l'algorithme vérifie donc la relation de récurrence . Par conséquent l'arbre des appels récursifs de l'algorithme est un arbre binaire qui comporte étages, et chaque étage a une complexité . Ainsi, par le master theorem, l'algorithme est en [3].
On sait aussi que tout algorithme nécessite Ω(n log n) étapes de calcul pour trouver deux points les plus rapprochés[2].
Si on suppose que la fonction partie entière est calculable en temps constant, alors le problème se résout en O(n log log n)[5]. Si on s'autorise des algorithmes probabilistes (et la fonction partie entière calculable en temps constant), alors le problème se résout en O(n) en espérance[6],[7].
L'algorithme diviser pour régner se généralise à toute dimension d, avec une complexité de O(n log n) à dimension fixée, mais avec une dépendance exponentielle en la dimension[8].
Ce problème de recherche est utilisé par les contrôleurs aériens pour repérer les avions les plus proches les uns des autres (l'espace considéré est ici à 3 dimensions), et ainsi prévenir le risque de collision[3].
L'algorithme de Michael O. Rabin pour ce problème est l'un des premiers algorithmes géométriques probabilistes[9].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.