Encontrar la distancia máxima entre (x, y) coordenadas

Estoy tratando de calcular la distancia máxima de Manhattan de una gran entrada 2D, las entradas consisten en (x, y) sy lo que quiero hacer es calcular la distancia máxima entre esas coordenadas En menos de O (n^2) tiempo, puedo hacerlo en O (n^2) pasando por todos los elementos algo así como:
* (distancia Manhattan entre dos puntos (X1, Y1) y (X2, Y2) es: | X1-X2 | + | Y1-Y2 |)Encontrar la distancia máxima entre (x, y) coordenadas

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

pero no va a trabajar de manera eficiente para grandes entradas :(
alguien tiene alguna idea para un mejor algoritmo

Fuente

2011-11-04 Anonymous

Hay solo dos casos a considerar, si solo consideramos resultados como Xi <= Xj.

Si Yi <= Yj, entonces la distancia es (Xj + Yj) - (Xi + Yi)
De lo contrario, la distancia es (Xj - Yj) - (Xi - Yi)

Por lo descomponen en estos casos, me he librado de la función de valor absoluto lo que es mucho más fácil razonar sobre las distancias.

Por lo tanto, simplemente elegimos puntos con un mínimo y un máximo de x+y, y calculamos la distancia. A continuación, elija puntos con un mínimo y un máximo de x-y, y calcule la distancia. Una de esas dos distancias es tu máximo.

Esto se puede hacer en O(n), que es óptimo de forma asintótica.

Fuente

2011-11-04 08:55:37

esto es justo lo que estaba buscando, gracias hombre :) –

-2

La distancia máxima estará entre los puntos más alejados unos de otros. Así que solo tienes que encontrar un punto con un máximo de X y un máximo de Y y luego encontrar un punto con un mínimo de X y un mínimo de Y y calcular la distancia entre ellos. No puede haber una gran cantidad de puntos que coincidan con los criterios .. pero al menos yu'll tener una mucho menor cantidad de puntos para comprobar

Fuente

2011-11-04 08:48:48

No, hacen que la coordinación con máxima X, podría no tener el máximo de Y! y es así también con el mínimo, considere estos: (7, -2), (-1,5), (3, -9) y muchos más, estos 3 desaprobarán su algoritmo –

la primera gran mejora sería:

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

ya que la distancia entre X e Y es lo mismo que la distancia entre Y y X. eso reduciría su cálculo a la mitad ...

Fuente

2011-11-04 08:48:59

Sí, eso es una mejora, pero aún así toma O (n^2) time :(que no funcionará para entradas muy grandes –

sí lo sé, solo estaba señalando la primera mejora obvia: reducir a la mitad el número de comparación sigue siendo una gran mejora. Todavía estoy pensando sobre una manera más rápida ... –

Es bastante sencillo y se puede calcular en O(n)

Vamos x1>x2 y y1>y2

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

Vamos x1>x2 y y1<y2

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

Ahora cambiar x1 con x2 y se toma la misma resultados.

Así que, en general, su solución es

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

Fuente

2011-11-04 09:08:43 pnezis

Oops, demasiado tarde, Dietrich ya respondió – pnezis

Sí, como Dietrich ha señalado a este –

Lo mejor que puede hacer con este tipo de preguntas es tratar de establecer algunos pequeños resultados que le ayudará con el problema general.

Por ejemplo, no es demasiado difícil determinar que para tres puntos, A, B y C, que tienen la condición de que B es entre (más sobre esto en un segundo) A y C, B lo harán nunca más lejos de un cuarto punto D que uno de A y C. Con la métrica de distancia euclidiana estándar, un punto se encuentra entre otros dos puntos si se encuentra en el segmento que los une. Para las mediciones de Manhattan no es tan simple, en parte porque el concepto de segmento no se entiende tan bien.

Una forma más general de la descripción de 'entre' es esta (usando la notación de que la distancia de A a B es | AB |): Un punto B es entre dos puntos A, C si | AB | + | BC | = | AC |

Se puede ver que en la distancia euclídea esto significa que B se encuentra en el segmento que une A y C.

En Manhattan distancia, esto significa que el punto B está contenido en el rectángulo definido por A y C (que por supuesto, podría ser un segmento recto si AC es paralelo a uno del eje).

Este resultado significa que para cualquier punto, si se encuentra entre dos puntos existentes, puede ser no más lejos de cualquier nuevos puntos que se añaden al conjunto de los dos que lo rodean.

Ahora, esta información no resuelve el problema para usted, pero sí le permiten deshacerse de muchos posibles futuros cálculos. Una vez que ha determinado que un punto se encuentra entre otros dos, no tiene sentido seguirlo.

Por lo tanto, puede resolver este problema mediante el seguimiento solamente los puntos extremos, y sin tener en cuenta ninguna que caen dentro.

Un ejercicio interesante para el observador casual

demostrar que puede tener un máximo de 4 puntos distintos tales que ninguno de los puntos son entre dos de los otros, en el sentido de Manhattan.

Con este segundo resultado, queda claro que solo necesitará rastrear hasta 4 puntos.

Algunos de los otros métodos ya presentados son probablemente más rápidos, ¡pero de esta manera es más divertido!

Crédito extra

Generalizar estas ideas a n dimensiones

Fuente

2011-11-04 09:28:49 Cogito

Encontrar la distancia máxima entre (x, y) coordenadas

Respuesta

Cuestiones relacionadas