algorithm - saldo - quiero saber cuantos puntos tengo en el carnet de conducir

Dados los puntos N, ¿cómo encontrar el número máximo de puntos que están en un círculo?

Question

Ayer, una pregunta interesante viene a la mente, Given N points, how do you find the maximum number of points that are on a circle?

¿Puedes sugerir algo más que fuerza bruta? ¿Qué es O (?)?

Answer 1

Excepto en los casos degenerados, tres puntos en un plano están en un círculo. Por lo tanto, un algoritmo O (n ⁴ ) obvio es enumerar todos los conjuntos de tres puntos que no están en una línea (O (n ³ )), calcular el centro del círculo (tal vez pueda haber dos, no estoy seguro) repasando los tres puntos, luego repita los otros puntos y verifique cuáles están en el mismo círculo, cuente y, una vez que el algoritmo haya terminado, informe el máximo.

Answer 2

Parece que hay un algoritmo O (N ^ 3 * log N) :)

iterate through all pairs of points - O(N^2)
    for each point of the rest compute radius of circle including that point and the selected pair of points - O(N)
    sort points by this radius - O(N*log N)
    select from the resulting array the biggest group with same radius - O(N)

En realidad, dado dos puntos y un radio, generalmente son posibles dos círculos, pero teniendo esto en cuenta (dividir cada grupo en) no cambiará la complejidad del algoritmo.