Dados N puntos en el plano real 2D, ¿cuál es el algoritmo más eficiente para encontrar la mayor cantidad de puntos que se encuentran en un círculo?

Answer 1

Solo quiero seguir el método de Ryan Beltran. Creo que mucha gente en este hilo ya habló sobre la siguiente observación:

• Si 3 puntos no están en una línea, entonces puedes decidir un círculo.
• Una forma de describir un círculo es un centro y un radio, por lo tanto (x, y, r).

Por lo tanto, el esquema de este algoritmo sería:

1. Haga una lista de todas las combinaciones posibles de 3 puntos y encuentre todos los círculos potenciales, que requieren O (N ^ 3). Siempre que encontremos un centro, tírelo a un mapa hash, es decir, la clave es un círculo o una tupla 3 (x, y, r), y el valor es un recuento, o cuántos de esos círculos hasta ahora. Dado que la inserción hash toma O (1), este paso lleva totalmente O (N ^ 3).
2. Ahora iteramos sobre todo el par clave-valor en el mapa hash, pero lo que enfocamos ahora es el conteo. Pensemos una pregunta: si hay k puntos en el mismo círculo, a través del paso 1, ¿cuántos círculos generan estos k puntos? Sería C (k, 3) = k * (k-1) * (k-2) / 6. Ahora, pensemos al revés: si obtenemos el conteo denotado como D, ¿cómo obtenemos k ? La respuesta corta es (piso ((D * 6) ^ (1/3)) + 2), pero dejaré la carta de prueba. Para cada par clave-valor, el tiempo de procesamiento es constante.

Por lo tanto, la complejidad total sería O (N ^ 3).

Espero poder reducir aún más la complejidad a O (N ^ 2) u O (N ^ 2 logN), pero hasta ahora no tengo ni idea.

Todos pueden examinar la exactitud de este algoritmo.

–

Probar:

¿Cómo podemos calcular k dado D?

Primero, demostramos que (k-1) ^ 3> k * (k-1) * (k-2) = C (k, 3) * 6 = D * 6> (k-2) ^ 3 dado k> = 1.

Luego llegamos a la conclusión de que k = piso ((D * 6) ^ (1/3)) + 2

Answer 2

En primer lugar, este puede no ser el algoritmo más eficiente. Como mínimo, quería poner esto como un punto de partida para las respuestas, ya que esto es lo que me vino a la mente como método obvio.

El algoritmo básico:

• Poner puntos en grupos de tres
• Encuentra el círculo que los conecta
• Encuentra todos los puntos que existen en este círculo

Estoy encontrando el círculo como si fuera una brújula y un borde recto, y quizás haya un algoritmo más eficiente para que esto nos proporcione algo de eficiencia lineal, pero no lo creo. Vea Cómo construir un círculo a través de 3 puntos con brújula y regla o regla para ver cómo estoy encontrando el círculo.

Pequeña advertencia aquí, supuse que no estás permitiendo un círculo con radio infinito, que esencialmente sería una línea. Si permite esto más allá de donde digo continuar, debe recorrer y encontrar otros puntos que se encuentran en esta línea. (verifique si la pendiente entre cada punto y uno de los puntos en el peine es igual a la pendiente1)

dejar que los puntos sean una lista de puntos con propiedades x e y

si la longitud de los puntos <= 3
longitud de retorno de puntos

la mayoría = 3; La respuesta es al menos 3

para peine en {combinaciones de 3 elementos de puntos}:

cuenta = 0; cantidad de puntos en este círculo

; Obtener las pendientes de dos acordes del círculo.
pendiente1 = (peine [0] .y – peine [1] .y) / (peine [0] .x – peine [1] .x)
pendiente2 = (peine [1] .y – peine [2] .y) / (peine [1] .x – peine [2] .x)
si pendiente1 == pendiente2
Hacer continuación ; Cambie esto si permite un radio infinito

; obtener los puntos medios de cada acorde
mid1 = {(comb [0] .x + comb [1] .x) / 2, (comb [0] .y + comb [1] .y) / 2}
mid2 = {(comb [0] .x + comb [1] .x) / 2, (comb [0] .y + comb [1] .y) / 2}

; obtener las ecuaciones para cada acorde perpendicular bisectriz
perp_slope1 = -1 / pendiente1
perp_slope2 = -1 / pendiente2
y_int_1 = mid1 [1] – perp_slope1 * mid1 [0]
y_int_2 = mid2 [1] – perp_slope2 * mid2 [0]

; encontrar intersección de bisectrices perpendiculares.
; este es el centro del circulo
center_x = (y_int_2 – y_int_1) / (perp_slope1 – perp_slope2)
center_y = perp_slope1 * center_x + y_int_1

; encontrar el radio del círculo
radio = ((center_x-comb [0] .x) ^ 2 + (center_y-comb [0] .y) ^ 2) ^. 5

por pnt en puntos
dist = ((center_x – pnt.x) ^ 2 + (center_y – pnt.y) ^ 2) ^ .5
si list == radio
cuenta = cuenta + 1
si cuenta> la mayoría
más = contar

volver más

Eficiencia (donde n es la cantidad de puntos):

El bucle principal for toma las combinaciones de puntos en grupos de 3. La cardinalidad de ese conjunto es igual a:

[matemáticas] C (n, 3) [/ matemáticas]

[matemáticas] = n! / 3! (n-3)! [/matemáticas]

[matemáticas] = (n) (n-1) (n-2) / ((3) (2) (1)) [/ matemáticas]

[matemáticas] = (n ^ 3 – 3n ^ 2 + 2n) / 6 [/ matemáticas]

Que tiene O (n) de n ^ 3

Sin embargo, empeora aún más porque dentro de ese ciclo tenemos que verificar cada punto para ver si se encuentra dentro de nuestro círculo. Por lo tanto, cada paso en el bucle tiene O (n) de n

y entonces todo el método tiene un O (n) de n ^ 4

Si alguien puede mejorar esto, adelante. Lo intentaré también.

Answer 3

Creo que hay un algoritmo directo con complejidad de tiempo O (N ** 2). El centro de un círculo que contiene dos puntos debe estar en la línea cuyos puntos son equidistantes de los dos puntos. Los puntos que se encuentran en la intersección del mayor número de estas líneas serían los candidatos para ser el centro del círculo con el máximo número posible de N puntos en él.