找到覆盖太空中大多数点的圆

Question

我正在接受一家高频交易公司的采访.他们问我一个算法O(n):

• 给出n空间点
• 给定一个返回平面点的哈希函数O(1),
• 找到覆盖空间中最多点的最佳匹配圆.

要求:

• 圆心必须有整数坐标,它的半径是3.
• 圆内的点不一定具有整数坐标

我用Google搜索并做了一些研究.有一个O(n)算法(来自普林斯顿大学的Chazelle的最佳圆圈放置),但它有点超出我的水平,理解并将其组合起来在10分钟内解释它.我已经知道O(n^2)和O(n^3)算法.

请帮我找一个O(n)算法.

Answer 1

我猜整数坐标约束显着简化了问题.对我来说这看起来像O(n):

- 制作空间中所有整数点的字典,并将条目设置为0.

- 对于每个数据点,找到半径为3的整数点,并将1添加到字典的相应条目中.这样做的原因是,可以是该特定数据点所在的圆的中心的点集是围绕该数据点具有相同半径的圆的整数限制.可以在位于长度为6的正方形上的所有点上进行搜索(认为并非所有点都需要明确地评估,因为这些内部的超立方体内部是肯定的).

- 返回对应于字典最大值的整数点,即大多数数据点位于圆内的中心.

编辑:我想有些代码比解释更好.这是与numpy和matplotlib一起工作的python.不应该太难读:

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 11 19:22:12 2013

@author: Zah
"""

from __future__ import division
import numpy as np
import numpy.random
import matplotlib.pyplot as plt
from collections import defaultdict
import timeit
def make_points(n):
    """Generates n random points"""
    return np.random.uniform(0,30,(n,2))

def find_centers(point, r):
    """Given 1 point, find all possible integer centers searching in a square 
    around that point. Note that this method can be imporved."""
    posx, posy = point
    centers = ((x,y) 
        for x in xrange(int(np.ceil(posx - r)), int(np.floor(posx + r)) + 1)
        for y in xrange(int(np.ceil(posy - r)), int(np.floor(posy + r)) + 1)        
        if (x-posx)**2 + (y-posy)**2 < r*r)
    return centers


def find_circle(n, r=3.):
    """Find the best center"""
    points = make_points(n)
    d = defaultdict(int)
    for point in points:
        for center in find_centers(point, r):
            d[center] += 1
    return max(d , key = lambda x: d[x]), points

def make_results():
    """Green circle is the best center. Red crosses are posible centers for some
    random point as an example"""
    r = 3
    center, points = find_circle(100)
    xv,yv = points.transpose()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.set_aspect(1)
    ax.scatter(xv,yv)
    ax.add_artist(plt.Circle(center, r, facecolor = 'g', alpha = .5, zorder = 0))
    centersx, centersy  = np.array(list(find_centers(points[0], r))).transpose()
    plt.scatter(centersx, centersy,c = 'r', marker = '+')
    ax.add_artist(plt.Circle(points[0], r, facecolor = 'r', alpha = .25, zorder = 0))
    plt.show()

if __name__ == "__main__":
    make_results()

结果: 绿色圆圈是最好的,红色的东西展示了如何选择中心的随机点.

In [70]: %timeit find_circle(1000)
1 loops, best of 3: 1.76 s per loop

In [71]: %timeit find_circle(2000)
1 loops, best of 3: 3.51 s per loop

In [72]: %timeit find_circle(3000)
1 loops, best of 3: 5.3 s per loop

In [73]: %timeit find_circle(4000)
1 loops, best of 3: 7.03 s per loop

在我真的很慢的机器上.行为显然是线性的.