La mejor manera de resolver un problema de distancia

Question

Hay un conjunto de puntos que son colineales. El problema es agregar un nuevo punto que se encuentra en la misma línea, por lo que la suma de la distancia desde el nuevo punto hasta los puntos existentes es mínima. (Supongamos que el punto se encuentra en una línea horizontal).

La solución pensé es:

1. Ordenar los puntos de acuerdo con sus coordenadas x (y no importa de todos modos).
2. Si el número de puntos es impar, coloque el nuevo punto en la misma coordenada que en el medio.
3. De lo contrario, coloque el punto en el punto medio de n/2 y n/2 + 1 puntos.

No puedo probar que el método anterior funcione. ¿Es correcto? ¿También hay alguna forma mejor de resolver esto?

Answer 1

Creo que la mediana es la respuesta correcta si queremos minimizar la suma de las distancias absolutas, que es la interpretación obvia. La media es correcta si queremos minimizar la suma de las distancias al cuadrado. Para los puntos en y = 0 y x = 0, 1, 2, 101 la media es 26 y podemos tomar la mediana para que sea 1.5. La suma de las distancias absolutas desde la media es 149 y la suma de las distancias absolutas desde la mediana es 102.

En la mediana, el número de puntos a la izquierda es el mismo que el número de puntos a su derecha. Moverse a la izquierda en una pequeña cantidad aumenta todas las distancias a los puntos a su derecha y disminuye todas las distancias a los puntos a la izquierda en la misma cantidad, sin cambios. Si se encuentra a un punto o más lejos de la mediana, puede disminuir la suma de las distancias absolutas moviéndose hacia el área donde hay más puntos.Esto disminuye la suma de las distancias de orginationg del área donde hay más puntos por más de lo que aumenta la suma de las distancias que se originan en el área donde hay menos puntos. Por lo tanto, si no estás en la mediana, puedes mejorar las cosas moviéndote Hacia eso. Este es un resultado bastante estándar en las estadísticas.

Answer 2

Bueno, ciertamente no necesita ordenarlos. Simplemente tome el promedio de sus coordenadas xey. Esto funcionará en N dimensiones siempre que sean colineales.

EDIT: me di cuenta de que estoy calculando la media. Está calculando la mediana, como se indica en otra respuesta, que probablemente sea más probable que obtenga la distancia mínima a todos los puntos.

EDIT2: La mediana es la respuesta correcta para un número impar de puntos. Para un número par de puntos, es cualquier punto a lo largo del segmento de línea más interna definido por el área con el mismo número de puntos en ambos lados.

Prueba (ish): Encontraste una respuesta correcta, pero para un número par de puntos hay muliple.

Para dos puntos cualquiera, cualquier punto en el segmento de línea entre esos puntos tendrá la suma de sus distancias para que ambos puntos sean iguales. Cualquier punto fuera de ese segmento de línea tendrá sus distancias mayores que en el segmento de línea.

Por lo tanto, para encontrar el punto con la distancia más pequeña desde todos los puntos colineales, debe descomponer el problema en conjuntos de dos puntos, es decir, segmentos de línea que están completamente contenidos en otros segmentos de línea. Luego, solo tome el segmento de línea más pequeño (o punto en el caso de un número impar de puntos) y elija un punto en ese segmento de línea. Todos los puntos en ese segmento de línea tendrán la distancia mínima de todos los puntos para esa configuración particular.

Si desea graficar esto, todas las distancias de los gráficos de puntos tendrá la misma forma:/ Para un segmento de línea, el gráfico de la distancia se verá así: _/

En esencia, desea agregar todos los gráficos de distancia y encuentra el mínimo.

Answer 3

Lo que sigue no es la mejor solución. Pero da el valor correcto.

1. En primer lugar encontrar el ángulo de la línea, gire todos los puntos de revertir de ese ángulo para convertirse en una línea horizontal
2. Ordenar todos los puntos X, puesto que y será constante después de la rotación
3. Que sea X (1), X (2), X (3), ... X (N)
4. A continuación, almacene la distancia calculada D (R) para cada R de 1 a N como [(2R-N) * X (R)] - [X (1) + X (2) + X (3) .. + X (R)] + [X (R + 1) + X (R + 2) + X (R + 3) .. . + X (N)]
5. Obtenga un mínimo D (R).
6. Gire hacia atrás X (R), Y al ángulo original.
7. Ese es su valor esperado.
8. Si en D (R) & D (R + 1) son iguales, entonces todos los puntos girados entre X (R), Y & X (R + 1), Y serán su valor esperado.
9. Interstingly si R está en la mitad, entonces la respuesta será mínima ya que el número de adiciones [X (1) + .. X (R)] y [X (R + 1) + .. X (N)] son ​​casi iguales entonces la diferencia es mínima, de lo contrario, si el número de adiciones en un lado es mayor, entonces la diferencia será mayor que el número de adiciones iguales. Del mismo modo, si hay un número par de puntos, todos los puntos entre (N)/2 y (N/2) +1 tendrán la misma distancia igual.
10. Por lo tanto, MEDIAN es la respuesta correcta.

Espero que esto funcione para usted.

Answer 4

¡Problema interesante!

Editar: Lo siguiente está mal, pero no entiendo dónde está mi error.

La solución mediana que explicó en su pregunta es una solución incorrecta.

Puesto que usted quiere probar la corrección, me gustaría tratar de resolver este problema de la siguiente manera:

En primer lugar, ya que todos los puntos están alineados, que fácilmente puede dividir en su X e Y-componente . Luego resolvemos el problema de forma independiente para X e Y. Supongamos que obtuvimos los valores V[0] to V[n-1] siendo n el número de puntos.

Ahora el problema es calcular la x para que SUM((V[0 ... n-1] - x)^2) se vuelva mínimo. Construimos el derivado 2*n*x - 2*SUM(V[0 ... n-1]).

Esto se convierte en 0 para -n * x + SUM(V[0 ... n-1]). Por consiguiente, x = SUM(V[0 ... n-1])/n.

Así que solo agregue todos los valores y divídalos por n para obtener la solución mínima correcta. Después de hacer esto para xey, obtienes el punto deseado.

Esto también es igual a la suposición que hice cuando pensé por primera vez sobre su problema y funciona para algunos valores que probé. Espero que esto ayude. :)

Answer 5

Esto se resuelve al encontrar la mediana. Consulte http://en.wikipedia.org/wiki/Geometric_median (sección "Propiedades"). Sería suficiente realizar los cálculos en las coordenadas xey. Cualquiera de los dos puede usarse siempre que las coordenadas a lo largo del eje seleccionado no sean constantes para la línea.

Answer 6

Creo que puede probarlo por inducción. Haré los impares, y puedes expandirlo:

Sin pérdida de generalidad, podemos decir que los puntos se encuentran a lo largo de la línea y = 0, y que el punto central está en (0, 0). Esto se debe a que las transformaciones afines, como las rotaciones y la traducción, no afectan las distancias relativas.

Vamos el conjunto de puntos en la línea de ser definido como P = {(x, 0) < = x es real} definir la distancia desde el punto X como suma (P => | P - X |)

Lemma 1: El punto central debe estar a lo largo de la línea y = 0. Suponga que el punto central está en (x, y) con y! = 0. Considere el punto (x, 0).

 
sum(P - (x,y)) = sum(sqrt((p-x)*(p-x) + (0-y)*(0-y))) 
       = sum(sqrt(p*p - 2xp + x*x + y*y)) 
       > sum(sqrt(p*p - 2xp + x*x + (0-0)*(0-0))) 
       = sum(P - (x,0)) 

Esto es una contradicción, por lo que y = 0 debe ser cierto.

Funda base de 1 elemento: Es un número impar de elementos, así que elígelo: (0, 0). Supongamos que hay un punto X = (x, 0) tal que x está más cerca. Entonces esto significa que | x - 0 | < (0 - 0), o eso | x | < 0, lo cual es imposible. Por lo tanto, (0, 0) es el punto central.

Caja base de 3 elementos: Es un número impar de elementos, por lo tanto, elija el punto medio: (0, 0). Sin pérdida de generalidad, que los otros dos puntos sean (un < 0, 0) y (b> 0, 0). Supongamos que hay un punto X = (x, 0) que está más cerca. Entonces esto significa que:

| x - 0 | + | x - a | + | x - b | < | 0 - 0 | + | 0 - a | + | 0 - b |

< =>

| x | + | x - a | + | x - b | < | a | + | b |

Sin embargo:

| x | + | x - a | + | x - b | > = | x | + | a | + | b | > = | a | + | b |, que contradice la suposición, por lo tanto, (0, 0) es el punto central.

Caja con N elementos (N impar). Supongamos que todos los conjuntos de puntos impares satisfacen las condiciones anteriores. Deje que P sea el conjunto con N elementos y organícelos de la siguiente manera:

{(a, 0), Q = {conjunto de elementos N-2, con centro en (0, 0)}, (b, 0)}

Supongamos que el punto central es X = (x, 0).

 
sum(P - X) = |x-a| + |x-b| + sum(Q - X) 
      > |x-a| + |x-b| + sum(Q - (0,0)) 
      >= |a| + |b| + sum(Q - (0,0)) 
      = sum(P - (0,0)) 

Lo que significa que la suposición se contradice, por lo que (0,0) debe ser el punto central.

Eso lo demuestra para todos los números impares. Los números pares deben ser similares.

Answer 7

Above, mcdowella, FryGuy y ShreevatsaR tenían ideas en mi respuesta a continuación.

Sea n la cantidad de puntos en la línea. Deje que los puntos sean p (1), ..., p (n), etiquetados de izquierda a derecha.

Caso n = 1. Es cierto.

Caso n = 2. Es cierto. Puedes elegir cualquier punto entre los dos puntos.

Caso n> = 3. Introduzca un sistema de coordenadas x-y. Gire el plano para que los puntos estén en el eje x.

El punto que minimiza la distancia a los otros puntos debe estar en el intervalo [p (1), p (n)], debido al siguiente razonamiento: Si estuviera a la izquierda de p (1), muévalo Derecha un poco (lo suficientemente pequeño para que x no golpee p (1)), disminuyendo la distancia. Del mismo modo, si estuviera a la derecha de p (n).

Elija cualquier punto x en la línea, no necesariamente uno de p (1), ..., p (n).

Sea D la suma de las distancias de x a los otros puntos.

Sea L el número de puntos a la izquierda de x. Del mismo modo, sea R el número de puntos a la derecha.

Hay tres subcampos.

Subcase 1: x es la mediana. Entonces L = R. Si movemos x una pequeña cantidad e a la izquierda, la suma de distancia se convierte en D - Le + Re + e = D + e> D. De manera similar, para mover hacia la derecha. Entonces la mediana da un mínimo local.

Subcase 2: x está a la izquierda de la mediana. Similar a la siguiente subcase.

Subcase 3: x está a la derecha de la mediana. Entonces L> = R. Hay dos puntos tales que x está en (p (i), p (i + 1)] (el punto final izquierdo está excluido, pero el derecho está incluido). Deje e = x - p (i)

Mueva x a la izquierda en e. Podemos hacer que x se convierta en p (i). La suma de distancia se convierte en D - Le + Re = D - (L - R) e < = D. Es decir, posiblemente disminuir D. no aumentarlo.

Nos mantenemos en movimiento xa la izquierda, posiblemente disminuyendo la suma distancia, y no aumentarla, hasta que x se convierte en el medio. Así que la mediana da un mínimo global.