找出所有给定圆覆盖的点

Question

找出所有给定圆覆盖的点

algorithmgeometry

3

给定n个圆形（n ≤ 1000），每个圆形的坐标为(x;y)，半径为r，其中(x;y)是圆心坐标，r是半径。x、y、r都不超过10^6。x、y、r可以是实数。

问题是要找出所有圆形覆盖的点(x;y)，或确定没有这样的点存在。点的坐标也可以是实数。

对此问题暂无思路，是否有人能提供帮助？

- ValeraGrinenko

http://mathoverflow.net/ 可能更合适。 - Jarod42

我投票关闭此问题，因为它应该发布在另一个堆栈交换网站上。 - JVApen

4

Mathoverflow是专门为数学家寻求帮助的问题而设立的。虽然这个问题也涉及到算法，但是在Stackoverflow/Algorithm上发问也是适当的。请注意，Mathoverflow更加偏重于数学领域的问题。 - Matt Timmermans

1

选择半径最小的圆。如果存在这样的点，则该点在该圆内。逐渐增加半径以查找重叠或无重叠。无重叠意味着不存在这样的点。利用任何重叠来减少可能包含特定点的区域。 - rossum

“查找点（x；y）”是什么意思？可能存在0个或无限多个这样的点。您是指具有给定坐标(x，y)的点吗？ - Yuri Ginsburg

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

假设您所说的圆是数学家所称的封闭圆盘，则可以使用简单的数据结构实现O(n²)时间复杂度的算法。

对于从1到n的k值，该算法会找到第一个k个圆盘的交点，假设这样的点存在。从第一个圆盘的中心开始。对于后续每个圆盘，检查当前点是否属于该圆盘。如果是，那就很好。如果不是，则交集为空或交集包含当前圆盘边界上的一个点（从当前点到所有圆盘的交集中的任意一点的线段必须穿过边界）。在这种情况下，通过将边界（一个圆）与之前的每个圆盘相交来找到新点，这是一个更容易处理的1D问题。

如果我们随机排列圆盘的顺序，则期望中可能速度更快，但我还没有证明。对于n ≤ 1000，希望O(n²)足够快。

Sharir（“平面圆盘集的交和最近点问题”，1985）可能给出了O(n log²n)时间复杂度的算法，但我无法从摘要中判断。