Todos los puntos con distancia mínima de Manhattan desde el resto de puntos determinados [Optimizado]

Question

¡El problema aquí es encontrar un conjunto de todos los puntos enteros que dé una suma mínima sobre todas las distancias de Manhattan desde un conjunto de puntos dado!

Por ejemplo:

vamos a tener un determinado conjunto de puntos {P1, P2, P3 ... Pn}

problema básico es encontrar un punto X decir que tendría suma mínima sobre todas las distancias desde los puntos {P1, P2, P3 ... Pn}.

es decir | P1-X | + | P2-X | + .... + | Pn-X | = D, donde D será el mínimo sobre todo X.

Avanzando un paso más, puede haber más de un valor de X que cumpla con la condición anterior. es decir, más de una X puede ser posible, lo que daría el mismo valor D. Entonces, tenemos que encontrar todas esas X.

Un enfoque básico que cualquiera puede pensar será encontrar la mediana de las entradas y luego la fuerza bruta las coordenadas que se mencionan en this post

Pero el problema con este enfoque es: si la mediana da dos valores que están muy separados, entonces terminamos forzando en bruto todos los puntos que nunca se ejecutarán en un tiempo dado.

Entonces, ¿hay algún otro enfoque que dé el resultado incluso cuando los puntos están muy separados (donde la mediana da un rango que es del orden de 10^9).

Answer 1

Si la mediana le da un intervalo del orden de 10^9, cada punto en ese intervalo es tan bueno como cualquier otro.

Dependiendo de lo que quiera hacer con esos puntos más adelante, puede devolver el rango o enumerar puntos en ese rango. No hay manera de evitarlo ..

Obviamente en dos dimensiones que obtendrá un rectángulo Bouding, en 3 dimensiones de un paralelepípedo etc ..

El resultado será siempre un producto cartesiano de delimitación de los rangos obtenidos para cada dimensión, para que pueda devolver una lista de esos rangos como resultado.

Answer 2

Dado que en manhattan la distancia cada componente contribuye por separado, también puede considerarlos por separado. La respuesta óptima es (mediana (x), mediana (y)). Necesitas mirar alrededor de este punto para encontrar soluciones enteras.

NOTA: No leí su pregunta correctamente mientras respondía. Mi respuesta aún es válida, pero probablemente usted ya sabía sobre esta solución.

Answer 3

Puede considerar X e Y por separado, ya que aumentan la distancia de manera independiente. Esto reduce la pregunta a encontrar, dado n puntos en una línea, un punto con la suma mínima de distancias a los otros puntos. Esto es simple: cualquier punto entre las dos medianas (inclusive) satisfará esto.

---

Prueba: Si tenemos un número par de puntos, habrá dos medianas. Un punto entre las dos medianas tendrá n/2 puntos a la izquierda y n/2 puntos a la derecha, y una suma total de distancias a esos puntos de S.

Si lo movemos un punto a la izquierda, S va a subir por n/2 (ya que nos estamos moviendo lejos de los puntos más a la derecha) y abajo por n/2 (ya que estamos moviéndose hacia los puntos más a la izquierda), por lo que en general S sigue siendo el mismo. Esto es cierto hasta que lleguemos al punto de la mediana más a la izquierda. Cuando movemos uno a la izquierda del punto mediano más a la izquierda, ahora tenemos (n/2 + 1) puntos a la derecha y (n/2 - 1) puntos a la izquierda, por lo que S sube dos. Continuar hacia la izquierda solo aumentará S más.
Por la misma lógica, todos los puntos a la derecha de la mediana más a la derecha también tienen una mayor S.

Si tenemos un número impar de puntos, solo hay una mediana. Utilizando la misma lógica que la anterior, podemos demostrar que tiene el valor más bajo de S.

Answer 4

Sí, también creo que para el número impar de N puntos en una cuadrícula, solo habrá un punto individual (es decir, el MEDIANO) que será como mínimo la suma de la distancia de Manhattan desde todos los demás puntos.

Para el valor par de N, el escenario será un poco diferente.

De acuerdo a mi si dos conjuntos X = {1,2} and Y= {3,4} su producto cartesiano habrá siempre 4.

es decir X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}. Esto es lo que he entendido hasta ahora.

En cuanto a la cantidad de valores EVEN, siempre tomamos los valores "MIDDLE TWO" como MEDIAN. Tomar 2 de X y 2 de Y siempre devolverá un producto cartesiano de 4 puntos.

Corrígeme si estoy equivocado.