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

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

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

Ответ 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)

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

Ответ 2

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