3.1 Algorithmes basés sur la méthode logarithmique
Les premiers algorithmes sont basés sur l’application de la méthode logarithmique de Bentley . Cette application est apparue pour la première fois dans Smid . (Voir aussi Schwarz .)
Laissez S être l’ensemble actuel de points dans ℝD, et laissez n dénoter sa taille. Écrire n dans le système de nombres binaires, n=∑i≥0ai2i, où ai ∈ {0,1}. Partitionner S (arbitrairement) en sous-ensembles : pour chaque i tel que ai = 1, il existe un sous-ensemble Si, de taille 2i. De plus, pour chaque tel i, il existe un nombre réel δi tel que d(S) ≤ δi ≤ d (Si) la structure de données est constituée de ce qui suit.
(1)
La paire la plus proche de S et sa distance δ
(2)
Pour chaque i tel que ai = 1, une δi -grille stockant les points de Si. Nous supposons que les cellules non vides de cette grille sont stockées dans un arbre de recherche binaire équilibré, triées lexicographiquement selon leurs coins « inférieurs gauches ».
On considère maintenant l’insertion d’un nouveau point p. Pour chaque i tel que ai = 1, on trouve la cellule de la δi-grille qui contient p ainsi que les 3D – 1 cellules voisines. Ensuite, nous calculons les distances entre p et tous les points de Si qui sont contenus dans ces cellules. Si nous trouvons une distance inférieure à δ, alors nous mettons à jour δ, et la paire la plus proche. Il reste à mettre à jour le reste de la structure de données. Soit j l’indice tel que a0 = a1 = … = aj – 1 et aj = 0. Soit Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 et δj := δ. Nous construisons une δj -grille pour l’ensemble Sj, et écartons les grilles pour l’ensemble S0, S1,… Sj – 1 (rendant ainsi implicitement ces ensembles vides).
Pour prouver la justesse de cet algorithme, notons que puisque d(S) ≤ δi, il suffit de comparer p avec tous les points de Si qui sont dans le voisinage de p- dans la δi-grille. Par conséquent, la paire la plus proche est mise à jour correctement. De plus, la nouvelle valeur Sj satisfait d(S ∪ {p}) ≤ δj ≤ d(Sj), et pour tout i > j, on a d(S ∪ {p} ≤ δi d(Si). Enfin, la structure de données mise à jour contient une grille stockant 2i points pour chaque i tel que la représentation binaire de n + 1 contient un un à la position i.
Nous analysons la complexité de l’algorithme d’insertion. Notons d’abord que puisque δi ≤ d(Si), le voisinage de p dans la δi -grille contient au plus un nombre constant de points de Si. Par conséquent, nous passons O(log n) temps pour chaque grille. Puisque la structure de données contient un nombre logarithmique de grilles, la première partie de l’algorithme d’insertion prend O(log 2n) temps.
Considérons la deuxième partie de l’algorithme, dans laquelle nous construisons la δj -grille. Cette étape prend O(|Sj |log |Sj|) temps, à cause du tri. Cependant, si nous stockons les points dans un ordre trié approprié, alors cette grille peut être construite en O(|Sj|) = O(2j) temps. (Voir pour les détails.) Puisque j peut prendre n’importe quelle valeur entre zéro et ⌊log n⌋, le temps d’insertion fluctue largement. Nous affirmons cependant que le temps amorti de la deuxième étape est borné par O(log n).
Pour prouver cette affirmation, supposons que nous commençons avec un ensemble vide S et que nous effectuons une séquence de n insertions. Soit kj le nombre de fois que lors de ces insertions, nous construisons une grille pour un sous-ensemble de taille 2j Alors kj est au plus égal au nombre d’entiers constitués d’au plus 1 + ⌊log n⌋ bits dont les j bits les moins significatifs sont égaux à un, et dont le (j + 1)-ième bit est égal à zéro. Autrement dit, on a
Le temps total passé pour la deuxième étape pendant les n insertions est borné par
ce qui prouve l’affirmation.
Nous avons montré que le temps d’exécution de l’algorithme complet de maintien de la paire la plus proche est borné par O(log 2n) temps dans le pire des cas plus O(log n) temps amorti par insertion. En utilisant des techniques standard (voir Overmars ), nous pouvons transformer la structure de données de sorte que la deuxième étape prenne un temps logarithmique dans le pire des cas. Par conséquent, nous avons une structure de données qui maintient la paire la plus proche en O(log 2n) temps le plus défavorable par insertion. La structure a une taille O(n).
Notez que la première étape de l’algorithme prend O(log 2n) temps, alors que la deuxième étape prend seulement O(log n) temps. Cela suggère qu’une amélioration est possible. En effet, au lieu d’écrire n dans le système numérique binaire, on utilise le système numérique de base log n. (Voir Overmars ou Schwarz .) De cette façon, les deux étapes prennent O(log 2n/log log n) temps, alors que l’espace utilisé reste linéaire.
Donc, nous avons une structure de données de taille linéaire qui maintient la paire la plus proche en O(log2 n /log log n) temps pire cas par insertion. Notez que l’algorithme utilise la fonction plancher afin de trouver la cellule de grille contenant le nouveau point p. En remplaçant la grille par une grille dégradée, l’algorithme peut être implémenté dans le modèle d’arbre de calcul algébrique.
Il est encore possible d’améliorer la structure de données ci-dessus. Considérons à nouveau la structure de données basée sur la représentation de n dans le système numérique binaire. L’observation principale est la suivante : Si nous insérons un point p, alors pour chaque i tel que ai = 1, nous trouvons la cellule du δi -gird qui contient p (plus les cellules voisines). En d’autres termes, nous effectuons des requêtes de localisation de points dans un nombre logarithmique de grilles, mais toujours avec le même point de requête p. Dans Schwarz et Smid , il est montré que la technique de cascade fractionnaire peut être étendue de sorte que toutes ces requêtes ensemble peuvent être résolues en O(log n log n) temps. Le problème principal est que nous avons des grilles avec des tailles de grille différentes. Par conséquent, il faut introduire un ordre sur les cellules de la grille qui soit « compatible » avec toutes ces tailles. Un tel ordre est défini. Par conséquent, la localisation du point p dans toutes les grilles nécessite O(log n) comparaisons. Cependant, comme l’ordonnancement est assez compliqué, chaque comparaison prend O(log log n) temps. Globalement, nous obtenons une structure de données de taille O(n) qui maintient la paire la plus proche en O(log n log n) temps amorti par insertion. Notez que nous avons besoin de la fonction floor pour ce résultat. Ce résultat peut probablement être obtenu dans le pire des cas, mais les détails seront fastidieux. Il n’est pas clair si l’ordonnancement sur les cellules de la grille peut également être défini si nous utilisons des grilles dégradées au lieu de grilles standard.
Nous mentionnons enfin une extension de la structure de données ci-dessus. La structure telle que décrite ci-dessus utilise fortement le fait que nous n’insérons que des points. Il s’avère cependant que la structure peut être adaptée pour traiter des mises à jour semi-online, telles que définies par Dobkin et Suri . Une séquence de mises à jour est dite semi-online si les insertions sont en ligne – c’est-à-dire qu’elles arrivent dans un ordre inconnu – mais que lorsqu’un point est inséré, on nous dit après combien de mises à jour à partir du moment de l’insertion il sera supprimé. Cette information supplémentaire sur les suppressions peut être utilisée pour garantir que lorsqu’un point est supprimé, il est toujours contenu dans une grille stockant un petit sous-ensemble. Comme la distance minimale peut augmenter lors d’une suppression, nous stockons des informations supplémentaires dans la structure de données pour mettre à jour efficacement la paire la plus proche. De cette façon, nous obtenons une structure de données de taille O(n) qui maintient la paire la plus proche en O(log 2n) temps le plus défavorable par mise à jour semi-online. Pour plus de détails, nous renvoyons le lecteur à Dobkin et Suri et Smid .