给定N个点，如何找到圆上最多的点？

Question

昨天，我想到了一个有趣的问题，给定 N 个点，如何找到一个圆上的最大点数？

除了暴力破解之外，您还能提出其他建议吗？什么是O（？）？

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³))，计算出线的中心圆（也许可以有两个，我不确定）遍历这三个点，然后迭代其他点并检查哪些点在同一个圆上，计数，并在算法完成后报告最大值。