Elija los puntos k más cercanos de los n puntos dados

Question

Se le asigna un conjunto de U de n puntos en el plano y puede calcular la distancia entre cualquier par de puntos en tiempo constante. Elija un subconjunto de U llamado C de modo que C tenga exactamente k puntos en él y la distancia entre los 2 puntos más lejanos en C sea lo más pequeña posible para k dada. 1 < k < = n

¿Cuál es la forma más rápida de hacer esto además de la obvia solución n-choose-k?

Answer 1

Una solución se muestra en Finding k points with minimum diameter and related problems - Aggarwal, 1991. El algoritmo descrito en la misma ha Duración: O(k^2.5 n log k + n log n)

Para aquellos que no tienen acceso al papel: el problema se llama k-diámetro y definido como

Encuentra un conjunto de k puntos con diámetro mínimo. El diámetro de un conjunto es la distancia máxima entre cualquier punto del conjunto.

Realmente no puedo dar una visión general sobre el algoritmo presentado, sino que incluye el cálculo de la (3k - 3) º orden diagrama de Voronoi de los puntos, y luego resolver el problema para cada uno de los O (kn) Voronoi establece (calculando conjuntos independientes máximos en algunos gráficos bipartitos) ... Supongo que lo que trato de decir es que no es muy trivial, y mucho más que una entrevista y este sitio :-)

Answer 2

Esto sigue siendo una idea desordenada, No estoy seguro de si realmente funciona No funciona. Dejando la respuesta incorrecta aquí para la posteridad.

For each point in U 
    make a list of the distance to each point in U 
    sort the list 
    add largest distance to a max-heap. 
while any of the lists have more than k elements 
    remove max of heap twice 
    remove corresponding elements from the two lists they came from 
    add the two newly exposed largest elements from those two lists to the heap 
Any of the lists left with k elements will list the elements in C 

Básicamente, se encuentran los dos puntos que en la actualidad parece que podría estar ambos en el subconjunto juntos, y que tienen la mayor distancia prudente y, a continuación, descarta su tanto estar en el subconjunto juntos. Repita hasta que se quede con una sola forma posible de formar un subconjunto de tamaño k.

Esto debería ser la complejidad del tiempo O ((n^2) log (n)) y la complejidad del espacio O (n^2).

Answer 3

Esto debería ser una buena solución aproximada si no tiene demasiados valores extremos

p = mean center (average x, y) of U 
M = U sorted by distance to p 
C = M[0:k] 

Answer 4

Dado que esta es una pregunta de la entrevista, aquí está mi oportunidad de una solución. (Como DCN señala más adelante, esto no está garantizado para devolver la solución óptima, aunque todavía debe ser una heurística decente. Buena captura, DCN!)

1. crear un conjunto S _p con una sola punto P.
2. Calcule la distancia entre cada punto en S _p y cada punto fuera de ella, luego agregue el punto con la distancia máxima más pequeña a S _p.
3. Repita 2. hasta que S _p tenga k puntos.
4. Repita 1-3 usando cada punto una vez como la P. inicial Tome la S _p que tiene la distancia máxima más pequeña.

hay puntos O (k) en S _p, y o puntos (n) fuera de él, por lo que encontrar el punto con la distancia máxima más pequeña es O (nk). Repetimos este k veces, y luego repetir el procedimiento entero n veces, por una complejidad global del O (n k).

Podemos mejorar en esto por el almacenamiento en caché la distancia máxima entre cualquier punto en S _p y cada punto exterior de S _p. Si maxDistanceFromPointInS[pointOutsideS] es, por ejemplo, una tabla hash O (1) que contiene la distancia máxima actual entre cada punto pointOutsideS y algún punto dentro de S _p, entonces cada vez que agreguemos un nuevo punto newPoint, establecemos maxDistanceFromPointInS[p] = Max(maxDistanceFromPointInS[p], distance(newPoint, p)) para todos los puntos p de S _p.Luego, encontrar la distancia máxima más pequeña es O (n), agregar un punto a S _p es O (n). Repetir este k veces nos da O ((n + n) k) = O (nk). Finalmente, repetimos el procedimiento entero procedimiento n veces, para una complejidad total de O (n k).

Podríamos mejorar la búsqueda de la distancia máxima más pequeña a O (1) usando un montón, pero eso no cambiaría la complejidad general.

---

Por cierto, se tardó una hora para escribir todo esto para arriba - no hay manera de que podría haber hecho esto en una entrevista.

Answer 5

Su posible en deterministic polynomial time aparentemente.

Pero no entiendo su algoritmo. Parece que los círculos que eligen son siempre uno de los puntos de entrada. ¿Puede alguien arrojar algo de luz sobre esto o explicar claramente lo que hacen (solo la sección 2 sería suficiente)?

Answer 6

El problema real que se le preguntó parece difícil. Si los puntos no estaban en el plano y tenían distancias arbitrarias, sería NP-hard por reducción de k-clique (tome un gráfico no ponderado arbitrario, y agregue bordes de infinito de longitud para bordes faltantes, y bordes de longitud 1 para bordes existentes - existe una camarilla de tamaño k siempre que los "puntos k más cercanos" tengan una distancia mutua máxima de 1 en lugar de infinito). Sin embargo, dado que los puntos están limitados a estar en el plano, por lo que dichas etiquetas de distancia están prohibidas, es posible que haya una solución. Al menos, parece susceptible de aproximación cerrada.

Si su entrevista significaba 'más pequeños puntos k diámetro del círculo que encierra', entonces el siguiente podría ser el algoritmo más rápido correcta que haya podido venir razonablemente con por sí mismo en una entrevista:

Para cada grupo de tamaño 3, calcular el círculo más pequeño que contiene estos puntos, y verifica si cada punto está contenido en este círculo. Si el número contenido es al menos k, actualice el diámetro mínimo en consecuencia.

Básicamente, este es un bucle dividido en cuatro partes para que el tiempo de ejecución sea O (n^4).