Ama*_*ain 7 algorithm computational-geometry
以下是careercup.com的Google访谈部分提出的问题:
在2d空间中给定2*n + 3个点,没有3个点共线且没有4个点位于圆上,
设计一个算法,该算法将找到一个圆圈,其中包含n个点,n在其外部,3个在其上.
我可以想到一个O(n ^ 4)解决方案:
a)选择任意3个点[以C(2n + 3,3)方式]并用这些(O(n ^ 3))做一个圆
b)现在每个圈,检查它内部是否有'n'点O(n)
由于这是一种天真的方法,我想问一下是否有更好的方法
来解决这个问题？即O(n log n)的顺序
这是一个O(n)解决方案.
设S为点集.设p是S的最左边的点.然后p在S的凸包上.设q是S点最小化从p到左边的光线和从p开始并经过q的光线之间的角度.p和q都可以在O(n)时间内找到.段pq是S的凸包的边缘,并且没有S点位于线pq的左侧.
取段pq的轴A. 包含p和q的圆的中心正好是轴A上的点.对于A上的每个点c,令C(c; p,q)为以c为中心并包含p和q的圆.如果c是远离左边的A点,则C(c; p,q)内部没有S点.如果c是远离右边的A点,则C(c; p,q)具有除p,q之外的所有S的点(p和q在圆上).如果我们从左向右移动c,则S的点逐个进入圆C(c; p,q)并且永不离开.所以介于两者之间,A上有一个点c,C(c; p,q)包含p,q和另外一个S点,并且内部恰好有n个其他点.
这可以在O(n logn)中清楚地找到:对于除p和q之外的S的每个点s,找到A上的点c,使得C(c; p,q)包含p,q和s.点c是轴A和段qs的轴的交点.请注意,当我们沿着A移动时,当我们经过c时,s进入了圆圈C(c; p,q).通过增加x坐标对这些中心进行排序并取(n + 1)-st,因为这是S的正好n个点已经在C(c; p,q)内部并且p,q和另外一个点开启的点C(C; p,q).要在O(n)中执行此操作,您会找到(n + 1)-st而不对它们进行排序.
您可以考虑使用四叉树：wiki 上的四叉树 然后使用此结构您可以扫描每个节点的邻近度。似乎有一个名为Query Range的函数。我认为，这个功能将使您比仅仅详尽地选择圆圈更加精确。
请注意，这不是解决方案，只是一个帮助您入门的想法。