Учитывая N баллов, как найти максимальное количество точек, которые находятся на окружности?

Question

Вчера возникает интересный вопрос, Given N points, how do you find the maximum number of points that are on a circle?

Можете ли вы предложить что-то кроме грубой силы? Что такое О (?)?

Answer 1

Кажется, что есть алгоритм 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)

Фактически заданные две точки и радиус двух окружностей, как правило, возможны, но, учитывая это (разбивая каждую группу на), не изменит сложности алгоритма.

Answer 2

За исключением вырожденных случаев, любые три точки на плоскости находятся на окружности. Таким образом, очевидный алгоритм O (n ⁴ ) состоит в том, чтобы перечислить все наборы из трех точек, которые не находятся на прямой (O (n ³ )), вычислить центр круга ( может быть, их может быть два, я не уверен), проходя три точки, а затем перебирая другие точки и проверяя, какие из них находятся на одной окружности, считайте, а после завершения алгоритма сообщите максимум.