考虑到N个点，如何找到在同一圆上的最大点数？

Question

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

除了暴力求解，你还能提出什么解决方案吗？ 时间复杂度是O(?)？

- user467871

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)

实际上，给定两个点和半径通常可以得到两个圆，但考虑到这一点（将每组分成两个），不会改变算法的复杂度。

- maxim1000

---

此外，排序还可以很好地处理数字精度问题，因为您可以设置公差，然后通过在排序列表中通过步进2个索引变量（标识当前最小和当前最大圆）来在线性时间内找到公差内的最大半径数量。 - j_random_hacker

不必使用半径，您可以通过圆心到PQ线的距离来表示通过点P和Q的圆，其中正值在一侧，负值在另一侧（所有可能的圆心都位于与PQ垂直且在P和Q之间的中点相交的线上）。这将唯一地将所有这样的圆的集合映射到实数。 - Jan Hudec

你能详细说明第二行吗？那两个点可以有无限多条穿过的圆，或者是我误解了你的意思？ - evgeny

Answer 2

除了退化的情况，平面上任意三点都在同一个圆上。因此，一个显然的O(n⁴)算法是列举出所有不在同一直线上的三点（O(n³)），计算通过这三个点的圆心（可能有两个，我不确定），然后迭代其他点并检查哪些点在同一条圆上，计数，等算法完成后，报告最大值。

- Antti Huima

---

我也是这样解决的，但我认为这只是暴力破解而已。 - user467871

考虑以下：任何由三个点形成的圆，如果与其他点重叠，将会被另一个三元组再次产生，因为你正在迭代所有这些点。你可以简单地记录特定圆被命中的次数，使得这个算法的时间复杂度为O(n^3)。 - user684934

将每个三元组的中心和半径存储起来，然后遍历该列表以查找任何给定中心和半径上的倍数。 - Will

@bdares：没错，但别忘了“缩小”那个计数。如果圆被击中n次，则必须有n =（k choose 3）对于某些k，因为任意3个k点将产生相同的圆。 k是我们想要的最终答案，而不是n。 - j_random_hacker

@bdares：不，计算机应该做那些重复性的工作。 - wnoise