0

给定平面中大致位置的 N 个点的列表（没有三个点共线），找到一个与 N 个原始点中的任何对都不共线的新点 p。

我们显然无法搜索平面上的每个点，我从找到可以与给定点形成的所有线的重合点开始，或者用它们做一个圆圈。我不知道如何检查所有的点。

在http://introcs.cs.princeton.edu/java/42sort/中发现的问题

我在一本著名的算法书中发现了这个问题，这意味着它是可以回答的，但我想不出一个最佳解决方案，这就是为什么我在这里发布它，以便如果有人知道他/她可以回答它

4

2 回答 2

0

您实际上可以使用简单的 O(nlogn) 算法解决它，然后我们将其改进为 O(n)。将 A 命名为最底部的点（如果出现平局，请选择 x 坐标较小的点）。您现在可以使用 CCW 按顺时针顺序对其余点进行排序。现在，当您从排序顺序处理每个点时，您可以看到在与点 A 和底轴具有不同角度的任意两个连续点之间（让这些点为 U，V），没有角度为 c 的点，且 U <= c <= V. 所以我们可以在本节中添加任何点，并保证它不会与集合中的任何其他点共线。所以，你只需要找到一对相邻的点就可以了。因此，在 O(n) 时间内找到与 A 的最小和第二个最小角度（这些应该不同），并选择它们之间的任何点。

于 2013-05-06T15:47:04.607 回答
0

我能想到的最好的算法是 N^2 算法。开始：

  1. 选择容差e来控制您愿意接近由集合中的点形成的线的距离。
  2. 计算一组点的凸包。
  3. 选择一条平行于凸包边之一的直线 L，在凸包外距离为3e 。
  4. 在L上选择一个点P，使得P在凸包在L上的投影之外。凸包在L上的投影是L的一个区间。P必须放在这个区间之外。
  5. 测试集合中的每一对点。对于由 2 个测试点形成的特定线 M 与围绕 P 的半径为2e的圆盘相交，将 P 沿 L 进一步移出，直到 M 不再与圆盘相交。通过 L 的构造，不可能有与 L 平行的圆盘相交的直线，所以这总是可以做到的。
  6. 如果 M 越过 P 越过 L，则将 P 移出该交叉点，再次移动到足以使 M 不穿过圆盘的距离。
  7. 完成所有这些之后，选择距离e处的点，在 P 处与 L 垂直。它可以与集合中的任何一条线共线。

步骤5中如何选择P沿L的下一个位置的细节留给你，

您可以进行一些明显的微不足道的拒绝测试，以便仅在测试线 M 与 L“足够平行”的情况下进行更昂贵的检查。

最后，我应该提一下，有可能将 P 推得足够远，以至于出现数值问题。在这种情况下，我可以建议的最好方法是在凸包之外尝试另一条线，距离至少为3e。

于 2012-04-09T18:33:36.663 回答