algorithm - Grupo más cercano de 3 puntos.

meta tags seo 2018

Question

¿Existe un algoritmo conocido y eficiente para encontrar el grupo más cercano de tres puntos en una nube?

Esto es similar al problema del par de puntos más cercano, pero estoy buscando tres puntos en lugar de dos.

Editar
La definición de "más cercano" afectará la complejidad del algoritmo. Como señaló Jack , encontrar el área del triángulo mínimo es 3sum-hard y en cualquier caso no es adecuado para mi aplicación.

Espero que exista un algoritmo más eficiente para encontrar el perímetro mínimo (es decir, AB | + | AC | + | BC |) triángulo o algo similar (por ejemplo, mínimo | AB | ² + | AC | ² + | BC | ². ) No conozco ninguna razón por la que esto deba ser tan complicado como la existencia de 3 puntos colineales en otra parte no afectaría el resultado.

Nota: mis puntos tienen ocho dimensiones, por lo que cualquier algoritmo que esté restringido a menos dimensiones no es adecuado.

Answer 1

El problema que mencionaste es la variación de 3sum problema difícil. Consulte los detalles en http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf .

Este problema también se puede expresar como encontrar un triángulo más pequeño a partir de puntos dados.

EDITAR:

Esencialmente, un problema difícil de 3sum significa que el límite inferior es O (n ^ 2). Puede haber pequeñas mejoras aquí y allá, pero no se puede hacer mucho.

Para este problema específico (triángulo más pequeño), consulte el capítulo 3 de http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf .

Answer 2

Esta es una forma específica del problema del vecino k más cercano , es decir, donde k = 3. La página citada no especifica la complejidad algorítmica, pero es bastante obvio ver que un enfoque ingenuo de calcular la distancia desde el punto seleccionado a todos los demás puntos, luego calcular la distancia desde ese punto a todos los demás puntos, así como la distancia desde nuestro punto original para el punto recién seleccionado es O (n ^k-1 ). Considere el pseudocódigo:

for pointB in searchSpace do:
    distanceAB := calculateDistance(pointA, pointB)
    for pointC in {searchSpace} - {pointB} do:
        distanceBC := calculateDistance(pointB, pointC)
        distanceCA := calculateDistance(pointC, pointA)
        if (distanceAB + distanceBC + distanceCA) < currentMin then:
            currentMin := distanceAB + distanceBC + distanceCA
            closestPoints := {pointA, pointB, pointC}

Tenga en cuenta que asumimos que el pointA ya se ha eliminado de searchSpace . Este es un algoritmo O (n ² ). Suponiendo que la dimensión es relativamente pequeña, o que la función calculateDistance crece linealmente o menos con la dimensión, esto da a la solución una restricción de tiempo decente. Las optimizaciones ciertamente se podrían tener, pero pueden no ser necesarias.

Si quieres ver un código real, wikipedia tiene many links a implementations .

Answer 3

Este problema es similar al problema clásico de encontrar el par más cercano en un conjunto de puntos. Puede adaptar los algoritmos O (n log n) en el peor de los casos que resuelven el problema del par más cercano para resolver este.

El problema específico fue presentado en la competencia Code Jam de Google. Aquí hay un resumen del análisis:

La cantidad de puntos puede ser bastante grande, por lo que necesitamos un algoritmo eficiente. Podemos resolver el problema en tiempo O (n log n) usando dividir y conquistar . Dividiremos el conjunto de puntos por una línea vertical en dos conjuntos de igual tamaño. Ahora hay tres casos para el triángulo de perímetro mínimo: sus tres puntos pueden estar completamente en el conjunto de la izquierda, completamente en el conjunto de la derecha, o pueden usar puntos de cada mitad.

Promover:

"Para encontrar el perímetro mínimo para el tercer caso (si es menor que p)":

1. Seleccionamos los puntos que están a una distancia de p / 2 de la línea de separación vertical.
2. Luego recorremos esos puntos de arriba a abajo y mantenemos una lista de todos los puntos en un cuadro de tamaño pxp / 2, con el borde inferior del cuadro en el punto considerado más recientemente.
3. A medida que agregamos cada punto al cuadro, calculamos el perímetro de todos los triángulos utilizando ese punto y cada par de puntos en el cuadro. (Podríamos excluir triángulos completamente a la izquierda o derecha de la línea divisoria, ya que ya se han considerado).

Podemos probar que la cantidad de puntos en el cuadro es como máximo de 16, por lo que solo debemos considerar, como mucho, un pequeño número constante de triángulos para cada punto.

Me parece que incluso podrías adaptar el método para trabajar en el caso | AB | ² + | AC | ² + | BC | ².

Answer 4

Hay un algoritmo obvio que funciona en O(n^2) .

1) realizar la triangluación de Delaunay - O(n log n) , por lo que obtenemos un gráfico plano.

Ya que es la triangulación de Delaunay, que maximiza el ángulo mínimo, está claro que los 3 puntos más cercanos deben estar conectados por al menos 2 bordes (¡pero no necesariamente tienen que formar el triángulo!). De lo contrario, habría más puntos cercanos o más ángulos cerrados.

2) para cada punto (vértice de la gráfica), examinamos cada par de bordes adyacentes y observamos los 3 vértices definidos por estos 2 bordes.

¿Cuánto tiempo tomará el paso 2)? Como la gráfica es plana, el número de bordes es <= 3n - 6, es decir, O(n) . Entonces, este paso tomará O(n^2) en el peor de los casos ( O(n) en el caso típico, donde el grado de cada vértice es limitado).

Entonces todo el algoritmo es O(n^2) . Tenga en cuenta que el paso 2) es de alguna manera una solución ingenua (fuerza bruta), así que creo que hay un espacio para mejorar (también, los pasos 1 y 2 probablemente podrían fusionarse de alguna manera).