Trouver la distance maximale entre les coordonnées (x, y)

Question

En essayant de calculer la distance maximale de manhattan d'une grande entrée 2D, les entrées sont constituées de (x, y) s et ce que je veux faire est de calculer la distance maximale entre ces coordonnées En moins de O (n^2) temps, je peux le faire en O (n^2) en passant par tous les éléments comme:
* (Distance Manhattan entre deux points (X1, Y1) et (X2, Y2) est: | X1-X2 | + | Y1-Y2 |)

for (0 -> n) 
    for (0-> n) 
     { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum } 

mais il ne fonctionnera pas efficacement pour les entrées très grandes :(
quelqu'un a une idée pour un meilleur algorithme

?

Answer 1

Il y a seulement deux cas à considérer, si nous considérons seulement des résultats tels que Xi <= Xj.

• Si Yi <= Yj, la distance est (Xj + Yj) - (Xi + Yi)
• Dans le cas contraire, la distance est (Xj - Yj) - (Xi - Yi)

, je me suis débarrassé de la fonction de valeur absolue en la décomposant dans ces cas ce qui rend beaucoup plus facile raisonner sur les distances. Donc, nous prenons simplement des points avec le minimum et le maximum x+y, et calculons la distance. Puis choisissez des points avec le minimum et le maximum x-y, et calculez la distance. Une de ces deux distances est votre maximum.

Cela peut être fait en O(n), ce qui est asymptotiquement optimal.

Answer 2

La distance maximale sera entre les points les plus éloignés les uns des autres. Il suffit donc de trouver le point avec le maximum X et le maximum Y, puis de trouver le point avec le minimum X et le minimum Y et calculer la distance entre eux. Il peut y avoir beaucoup de points qui correspondent à vos critères .. mais au moins yu'll ont beaucoup moins de quantité de points pour vérifier

Answer 3

la première grande amélioration serait:

for (X: 0 -> n) 
    for (Y: X -> n) 
     { compute the distance between X and Y } 

puisque la distance entre X et Y est la même que la distance entre Y et X. cela réduirait votre calcul de moitié ...

Answer 4

Il est assez simple et peut être calculé O(n)

Laissez x1>x2 et y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2) 

Laissez x1>x2 et y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2) 

changer maintenant x1 avec x2 et vous prenez la même résultats.

Donc, en général votre solution est

max ((max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi))) 

Answer 5

La meilleure chose à faire avec des questions comme celle-ci est d'essayer d'établir quelques petits résultats qui vous aideront avec le problème dans son ensemble.Par exemple, il n'est pas trop difficile de déterminer que pour trois points, A, B et C, qui ont la condition que B est entre (plus de détails dans une seconde) A et C, B ne jamais être plus éloigné d'un quatrième point D que l'un de A et C. Avec la métrique euclidienne standard de la distance, un point est entre deux autres points s'il se trouve sur le segment qui les relie. Pour les mesures de Manhattan, ce n'est pas si simple - en partie parce que le concept d'un segment n'est pas aussi bien compris. Une manière plus générale de décrire 'entre' est la suivante (en utilisant la notation que la distance de A à B est | AB |): Un point B est entre deux points A, C si | AB | + | BC | = | AC |

On peut voir que la distance euclidienne cela signifie que B se trouve sur le segment joignant A et C

Dans distance de Manhattan, cela signifie que le point B est contenu dans le rectangle défini par A et C (qui bien sûr pourrait être un segment droit si AC est parallèle à l'un des axes).

Ce résultat signifie que pour tout point, s'il se trouve entre deux points existants, il ne peut être plus éloigné des nouveaux points ajoutés à l'ensemble que les deux qui l'entourent. Maintenant, cette information ne résout pas le problème pour vous, mais elle vous permet de jeter beaucoup de calculs futurs potentiels. Une fois que vous avez déterminé qu'un point est entre deux autres, il est inutile de le suivre. Ainsi, vous pouvez résoudre ce problème en ne suivant que les points les plus éloignés et en ignorant ceux qui s'y trouvent.

Un exercice intéressant pour l'observateur occasionnel

Prouvez que vous pouvez avoir plus de 4 points distincts tels qu'aucun des points sont entre deux des autres, dans le sens Manhattan.

Avec ce deuxième résultat, il devient clair que vous aurez seulement besoin de suivre jusqu'à 4 points.

Certaines des autres méthodes déjà présentées sont probablement plus rapides, mais c'est plus amusant!

Extra Credit

Généraliser ces idées n dimensions