昨天,我想到了一个有趣的问题,给定N个点,如何找到最多在一个圆上的点的数量?
除了暴力求解,你还能提出什么解决方案吗? 时间复杂度是O(?)?
看起来有一个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)
实际上,给定两个点和半径通常可以得到两个圆,但考虑到这一点(将每组分成两个),不会改变算法的复杂度。
除了退化的情况,平面上任意三点都在同一个圆上。因此,一个显然的O(n4)算法是列举出所有不在同一直线上的三点(O(n3)),计算通过这三个点的圆心(可能有两个,我不确定),然后迭代其他点并检查哪些点在同一条圆上,计数,等算法完成后,报告最大值。