Seleccionar los puntos más dispersos de un conjunto de puntos

¿Existe algún algoritmo (eficiente) para seleccionar un subconjunto de puntos de un conjunto de puntos ( ) de modo que "cubran" la mayor parte del área (sobre todos los subconjuntos posibles de tamaño )?$M$$N$$M < N$$M$

Supongo que los puntos están en plano 2D.

El ingenuo algoritmo es simple, pero prohibitivo en términos de complejidad temporal:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Estoy buscando un método más eficiente o incluso aproximado.

Ejemplo, aquí hay un plano con algunos puntos aleatorios:

Para , espero seleccionar puntos como estos:$M=5$

Tenga en cuenta que los puntos seleccionados (rojo) están dispersos por todo el plano.

Encontré un artículo " SELECCIÓN EFICIENTE DE PUNTOS CLAVE DISTRIBUIDOS ESPACIALMENTE PARA EL SEGUIMIENTO VISUAL " que está relacionado con este problema. Sin embargo, esto supone que los puntos están ponderados.

Aquí hay una solución aproximada. Como N es tan grande y M es tan pequeño, ¿qué tal lo siguiente?

1. Calcule el casco convexo de N
2. Seleccione hasta M puntos del casco que satisfagan sus criterios de distancia máxima.
3. Si el Paso 2 lo deja con menos de M puntos, seleccione 1 punto del interior que maximice su distancia de los puntos seleccionados previamente.
4. Repita el paso 3 hasta que el número de puntos seleccionados sea M

La intuición detrás de esto es que, dado que N >> M , y desea puntos lo más alejados entre sí como sea posible, es probable que estén cerca de los bordes de los datos, por lo que podría comenzar con el casco y luego iterativamente trabaja desde allí.

Además, al comenzar con el casco, reduce su búsqueda inicial de N a N ^1/2 .

ACTUALIZAR

Si los pasos 3 y 4 anteriores están tardando demasiado (ya que está probando iterativamente el interior de su conjunto de datos), se me ocurrieron dos ideas más para acelerar su problema.

1. Búsqueda aleatoria : supongamos que encontró puntos P en el casco en el Paso 2. Luego, dibuje aleatoriamente puntos M - P desde el interior. Seleccione el mejor conjunto después de X pruebas.
2. Recocido simulado : calcule el cuadro delimitador más pequeño que cubre su conjunto de datos (no tiene que estar alineado con los ejes, podría inclinarse). Luego defina un conjunto de M puntos de cuadrícula distribuidos uniformemente en ese cuadro delimitador. Tenga en cuenta que estos puntos no coinciden necesariamente con ninguno de sus puntos del conjunto de datos. Luego, para cada punto de la cuadrícula, encuentre los vecinos k -nearest en su conjunto de datos. Revise cada combinación de M x k y seleccione la que satisfaga sus criterios de distancia máxima. En otras palabras, está utilizando la cuadrícula inicial como arranque para encontrar una buena solución inicial.

$N$$M$

$M$$M$

$M$$1$$M=3,4,5$

$M=3$$1$$M=4$$M=5$$1$

Si deseamos evitar la selección predominante de puntos en la periferia, un objetivo diferente puede ser útil. La maximización de la distancia mínima entre puntos es un criterio de este tipo. Los problemas relacionados se han abordado en StackOverflow , en Computer Science SE , en Math.SE y en MathOverflow .

$M$$D$$M$$D$

OK, entonces desea seleccionar M puntos de un conjunto dado de N puntos en el plano euclidiano, de modo que la suma de distancias por pares de los puntos seleccionados sea máxima, ¿correcto?

El algoritmo de búsqueda local estándar es bastante rápido y ofrece una aproximación bastante buena. El tiempo de ejecución es lineal en N y cuadrático en M. Su relación de aproximación es 1 - 4 / M. Esto significa que la relación mejora a medida que M aumenta. Por ejemplo, para M = 10 obtiene el 60% del valor óptimo, y para M = 50 obtiene el 92% del valor óptimo.

El algoritmo funciona también para espacios euclidianos de dimensión general. En este caso, el problema es NP-hard. Pero en el avión, no se sabe si es NP-duro.

La fuente es este artículo . ¡Espero que esto ayude! Mejor Alfonso

Una solución es:

• $O(n)$

• Haga M puntos artificiales incluso distribuidos dentro de este rectángulo delimitador, algunos M son más difíciles que otros. En su caso, cuatro en las esquinas del rectángulo y uno en el centro

• $O(n(log(n)))$

• $O(m(log(n)))$

$O(n(log(n)))$$\sqrt{M} \in \mathbb{N}$