Toutes les paires de points les plus proches avec une distance minimale dans un plan.

Question

Je dois trouver toutes les paires de points les plus proches dans un plan à partir d'un ensemble donné.

J'ai implémenté avec succès un algorithme naïf O(n²) similaire à cette fonction pseudo-code, où set est une liste de tous les points en entrée, count est le compte de tous les points sur l'entrée, qui retourne dist qui est la distance minimale trouvée et result est la liste de toutes les paires de points avec une telle distance.

function naive(Points[] set, int count)
    result = []
    distance = INF

    for i=0 to count-1:
        for j=i+1 to count:
           newDistance = distance(set[i], set[j])
           if newDistance < distance:
              result = []
              result.append({set[i], set[j]})
           else if newDistance == distance:
              result.append({set[i], set[j]})

   return (dist, result)

Cette solution fonctionne bien, mais elle est, grâce à la haute O(n²) complexité, très lent pour les grandes entrées. Je veux trouver une solution plus rapide et optimisée. O(n logn) solution en utilisant un algorithme récursif de division et de conquête basé sur cet article Cette approche fonctionne bien pour la plupart des entrées, mais comme elle n'itère pas à travers tous les points, elle échoue sur des entrées comme celle-ci (l'ordre des paires et l'ordre des points à l'intérieur des paires n'ont pas d'importance) :

Input:
{A[0,0], B[1,0], C[1,1] D[0,1]}

Current (wrong) output:
{A[0,0], D[0,1]}, {B[1,0], C[1,1]}

Desired output:
{A[0,0], B[0,1]}, {A[0,0], D[0,1]}, {C[1,1], B[1,0]}, {C[1,1], D[1,0]}

et aussi parce que c'est récursif, la pile déborde facilement pour les entrées plus importantes. Quelle est la meilleure façon de résoudre ce problème ?

Merci.

Answer 1

Mais vous n'avez pas besoin de tout comparer à tout le reste. Pour une paire de points donnée, imaginez qu'ils se trouvent sur la diagonale d'un rectangle [le rectangle étant aligné sur les axes de coordonnées] de longueur d .

• Si la pente est positive :
  • tout autre point situé à gauche de la ligne x = d sera plus éloigné et ne devrait pas être envisagé.
  • tout autre point situé sous la ligne y = d sera plus éloigné et ne devrait pas être envisagé.
• Si la pente est négative :
  • tout autre point qui se trouve à droite de la ligne x = d sera plus éloigné et ne devrait pas être envisagé.
  • tout autre point situé sous la ligne y = d sera plus éloigné et ne devrait pas être envisagé.

Des contraintes similaires peuvent être imaginées pour vous donner une boîte de délimitation dans chaque cas, ce qui devrait servir à éliminer un grand pourcentage de points à prendre en compte dans votre boucle interne, à moins que vous n'ayez une constellation particulièrement dense.

Il est certain qu'il faut une bonne dose de programmation dynamique pour obtenir des temps d'exécution raisonnables pour les grands ensembles.

Answer 2

La meilleure solution peut différer selon la façon dont les points sont distribués. L'une des approches consiste à découper le carré en de nombreux petits sous-carrés, choisis de manière à ce que chaque sous-carré ait environ 1 point en moyenne. Ensuite, on associe les points au sous-carré correspondant. Enfin, pour un point donné, il suffit de considérer les sous-carrés les plus proches pour trouver le plus proche voisin (en confirmant le statut de voisin en vérifiant tous les sous-carrés qui pourraient éventuellement contenir un point plus proche).

Answer 3

En ce qui concerne la première question. Je peux me tromper, mais je peux vous donner un indice.

Disons que vous avez 1000 points. Vous les divisez en 4 groupes de 250 points, puis vous faites 500 ensembles d'éléments à partir de toutes les paires de groupes. Dans ce cas, chaque paire de points sera couverte par une moitié (paire de groupes). Et n'oubliez pas de conserver toutes les valeurs min, pas une seule à chaque itération de la récursion.

De plus, comme vous devez effectuer un regroupement à chaque fois que vous divisez un ensemble, vous augmentez la complexité ici, donc vous pouvez considérer "lent". O(n²) pour les petits ensembles, de sorte que la solution réelle sera une combinaison des éléments suivants O(n log n) y O(n²) .

Pour la deuxième question, je ne peux suggérer qu'un moyen général d'éviter la récursion. Si vous avez assez de mémoire, utilisez la programmation dynamique, c'est-à-dire gardez tous les résultats précédents en mémoire et continuez jusqu'à ce que vous ayez rempli votre tableau avec tous les paramètres possibles. Ainsi, au lieu de faire un appel récursif, vous prenez simplement la valeur de votre tableau. Et bien sûr, vous devez recommencer jusqu'à ce que vous n'ayez plus de valeurs vides dans le tableau. La réalisation est différente d'une tâche à l'autre, vous devez donc réfléchir à la manière de mettre en œuvre cette tâche.