Distance la plus courte entre un point en A et un point en B

Étant donné deux ensembles et contenant chacun points disjoints dans le plan, calculez la distance la plus courte entre un point dans et un point dans , c'est-à-dire .$A$$B$$n$$A$$B$$\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \}$

Je ne sais pas si j'ai raison, mais ce problème est très similaire aux problèmes qui peuvent être résolus par programmation linéaire en géométrie computationnelle. Cependant, la réduction à LP n'est pas simple. De plus, mon problème semble lié à la recherche de la condition la plus mince entre deux ensembles de points qui peuvent évidemment être résolus par LP dans $O(n)$ dans un espace à deux dimensions.

J'ai une solution qui peut sembler un peu compliquée, mais qui devrait être plus efficace que la recherche par force brute naïve :$\mathcal O(n^2)$

1. laissez être l'axe entre les centres de masse de et .A $v$$A$$B$
2. Triez les points en et long de cet axe respectivement dans l'ordre décroissant et croissant, ce qui donne les séquences , , ..., et , , ..., .B a 0 a 1 a n b 0 b 1 b $A$$B$$a_0$$a_1$$a_n$$b_0$$b_1$$b_n$

Le reste est en pseudo-code pour le rendre plus clair:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

Autrement dit, en pré-triant les points le long de , vous pouvez filtrer les paires qui ne seront jamais à l'intérieur de de l'autre puisque long de sera toujours.d b k - a j v ≤ ‖ b k - a j$v$$d$$b_k-a_j$$v$$\le \|b_k-a_j\|$

Dans le pire des cas, c'est toujours , mais si et sont bien séparés, cela devrait être beaucoup plus rapide que cela, mais pas mieux que , ce qui est nécessaire pour le tri.$\mathcal O(n^2)$$A$$B$$\mathcal O(n\log n)$

Mise à jour

Cette solution n'est nullement sortie d'un chapeau. C'est un cas particulier de ce que j'utilise dans les simulations de particules pour trouver toutes les paires de particules en interaction avec le binning spatial. Mon propre travail expliquant le problème plus général est ici .

Quant à la suggestion d'utiliser un algorithme de balayage de ligne modifié, bien que intuitivement simple, je ne suis pas convaincu que ce soit dans lorsque des ensembles disjoints sont considérés. Il en va de même pour l'algorithme randomisé de Rabin.$\mathcal O(n\log n)$

Il ne semble pas y avoir beaucoup de littérature traitant du problème de paire la plus proche dans disjoints, mais je l' ai trouvé ce qui ne prétend pas à être sous , et ce qui ne semble pas pour faire des réclamations sur quoi que ce soit.$\mathcal O(n^2)$

L'algorithme ci-dessus peut être vu comme une variante du balayage plan suggéré dans le premier article (Shan, Zhang et Salzberg), mais au lieu d'utiliser l' axe et aucun tri, l'axe entre les ensembles est utilisé et les ensembles sont traversés dans l'ordre décroissant / croissant.$x$

Vous pouvez adapter l' algorithme de balayage de ligne de la "paire la plus proche" qui est .$O(n \log n)$

Le seul changement que vous devrez faire est d'ignorer les paires qui appartiennent au même ensemble.

Edit: Ce n'est en fait pas simple (ou même possible) comme je l'ai décrit. Voir les commentaires pour discussion.

L'idée dans des problèmes comme celui-ci est de créer une structure ordonnée à partir de l'un des ensembles qui permet des requêtes efficaces du plus proche voisin. L'article classique qui présentait une structure de requête O (log n) pour une dimension arbitraire était le suivant:

Shamos et Hoey sur les solutions Voronoi

Un certain nombre d'autres partitions spatiales basées sur les idées des tesselations de Delauney ont été créées depuis lors, et elles se traduisent également par une variété de descriptions de balayage sous-spatial. Notez que la méthode Voronoi tomberait également sous une description générale de division et de conquête en raison de son partitionnement plan qui fait l'étape de construction O (n log n).

Ainsi, la solution de base à ce problème est:

1. Prenez l'ensemble A et créez la structure de requête efficace du voisin le plus proche de votre choix. Cette étape de construction est O (n log n) [voir théorème 4].
2. Pour chaque élément de B, interrogez la structure A pour le plus proche voisin. Chaque requête est O (log n) [voir théorème 15, dimension fixe], donc le temps total de requête pour tous les points de B est O (n log n).
3. Lorsque le résultat du point A le plus proche de chaque B est récupéré, placez-le dans une structure ordonnée sur la distance. C'est O (log n) insérer chaque résultat, ou O (n log n) pour tous.
4. Lorsque tous les B ont été examinés, vous pouvez rapidement (O (1)) obtenir le point B dans la structure ordonnée avec la plus petite distance voisine à un point en A.

Comme on peut le voir en regardant la complexité de chaque étape, la complexité totale est O (n log n). Pour le lecteur moderne qui ne regarde pas les articles classiques, cela est couvert dans de nombreux livres d'algorithmes, par exemple "The Algorithm Design Manual" de Skiena.

Je ne sais pas si j'ai raison, mais ce problème est très similaire aux problèmes qui peuvent être résolus par programmation linéaire en géométrie computationnelle. Cependant, la réduction à LP n'est pas simple. De plus, mon problème semble lié à la recherche de la condition la plus mince entre deux ensembles de points qui peuvent évidemment être résolus par LP dans un espace à 2 dimensions.

$O(n*\log{n})$

Nous allons réduire l'instance du problème de distinction d'élément E à C.

• $S = \{a_1, a_2, a_3,...,a_n\}$
• $\epsilon$
• $\{(a_i,0) : 1 \leq i \leq n\}$$B = \{(a_i + \epsilon) : 1 \leq i \leq n\}$
• $O(n)$
  • $S$$\epsilon$

$O(n*\log{n})$