B*****t
发帖数: 335 | 1 二维平面上有一堆点，坐标都是整数
1. 寻找一个圆，使圆周上经过的点最多
有没有比O(N^3)更好的算法？
2. 给定圆的半径r，把这圆放在什么位置可以覆盖最多的点？
有没有比O(N^2logN)更好的算法？
3. 包含所有点的最小的圆的半径是多少？
我能想到的方法，从3个点开始，每次加一个点进去，并维持一个最小圆，直到所有的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？ |
k***e
发帖数: 556 | 2 几何题目太难了
我觉得被问到的可能性非常非常小
的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？
【在 B*****t 的大作中提到】
: 二维平面上有一堆点，坐标都是整数
: 1. 寻找一个圆，使圆周上经过的点最多
: 有没有比O(N^3)更好的算法？
: 2. 给定圆的半径r，把这圆放在什么位置可以覆盖最多的点？
: 有没有比O(N^2logN)更好的算法？
: 3. 包含所有点的最小的圆的半径是多少？
: 我能想到的方法，从3个点开始，每次加一个点进去，并维持一个最小圆，直到所有的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？
|
B*****t
发帖数: 335 | 3 hehe, the 1st one has been asked for several times. the interviewers seem to
look for a O(N^2) or even O(N) solution. but I just couldnot find an answer
yet.
【在 k***e 的大作中提到】
: 几何题目太难了
: 我觉得被问到的可能性非常非常小
:
: 的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？
|
k***e
发帖数: 556 | 4 哪个公司？
应该是paper上解决的题目，谁有兴趣去找一下？
整点有什么用处？圆心可能不在整点上
to
answer
【在 B*****t 的大作中提到】
: hehe, the 1st one has been asked for several times. the interviewers seem to
: look for a O(N^2) or even O(N) solution. but I just couldnot find an answer
: yet.
|
B*****t
发帖数: 335 | 5 I don't know which company, the 1st problem is from the "Quant 版面". I
restrict integer coordinates for each points to make the problems easier.
【在 k***e 的大作中提到】
: 哪个公司？
: 应该是paper上解决的题目，谁有兴趣去找一下？
: 整点有什么用处？圆心可能不在整点上
:
: to
: answer
|
l*y
发帖数: 21010 | 6 这是computational geometry的题目吧
minimum enclosing ball
的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？
【在 B*****t 的大作中提到】
: 二维平面上有一堆点，坐标都是整数
: 1. 寻找一个圆，使圆周上经过的点最多
: 有没有比O(N^3)更好的算法？
: 2. 给定圆的半径r，把这圆放在什么位置可以覆盖最多的点？
: 有没有比O(N^2logN)更好的算法？
: 3. 包含所有点的最小的圆的半径是多少？
: 我能想到的方法，从3个点开始，每次加一个点进去，并维持一个最小圆，直到所有的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？
|
z*******e
发帖数: 122 | 7 对于第3个题目，找包含所有点的最小圆的半径，我觉得可以先找到一个convex hall
包含所有的点（在CLRS上有nlogn的算法）,然后求这个convex hall的外接圆。 |
s********f
发帖数: 510 | 8 minimal enclosing circle 问题
http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
【在 z*******e 的大作中提到】
: 对于第3个题目，找包含所有点的最小圆的半径，我觉得可以先找到一个convex hall
: 包含所有的点（在CLRS上有nlogn的算法）,然后求这个convex hall的外接圆。
|
B*****t
发帖数: 335 | 9 Thanks for the link!
Do you have any idea to solve the other 2?
【在 s********f 的大作中提到】
: minimal enclosing circle 问题
: http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
|
