10

这是一个有趣的练习：

令 P 是一个简单但不一定是凸多边形，q 是一个不一定在 P 中的任意点。

设计一种有效的算法来找到一条源自 q 且与 P 的最大边数相交的线段。

换句话说，如果站在 q 点，你应该把枪瞄准哪个方向，这样子弹才能穿过最多的墙壁？

子弹穿过 P 的一个顶点，只获得一堵墙的功劳。

O(n log n) 算法是可能的。n 是顶点或边的数量，因为它是一个多边形，边的数量大致等于顶点的数量。

这是我的想法：

首先将 q 与 P 中的所有顶点（假设有 N 个顶点）连接起来。将有 N 行，或 N-1 对行。

最后的射击线必须在这些对之间。所以我们必须找到包含最多边数的对。

我不认为这个解决方案是 O(n log n)。

有任何想法吗？

4

2 回答 2

10

好吧，首先将点坐标转换为以 P 为中心的极坐标系。

  • 不失一般性，我们选择顺时针方向作为角度坐标的特殊方向。
  • 现在让我们沿着多边形的所有边按顺序进行循环行走，让我们注意这些边的起点和终点，沿着相对于 P 的顺时针方向行走。
  • 让我们将这种边缘的终点称为“屁股”，将起点称为“头”。这一切都应该在 O(n) 中完成。现在我们必须对这些头和屁股进行排序，所以使用快速排序可能是O(nlog(n)). 我们按照它们的角度 (φ) 坐标从最小的 φ 向上对它们进行排序，确保在 φ 坐标相等的情况下，头部被认为小于屁股（这对于遵守问题的最后一条规则很重要）。
  • 完成后，我们将从最小的 φ 开始遍历它们，每当遇到枪托时递增运行总和，每当遇到头时递减，注意全局最大值，这将是 φ 坐标上的间隔。这也应该在 O(n) 中完成，因此总体复杂度为O(nlog(n)).

现在你能告诉我你为什么要问这种问题吗？

于 2012-05-06T21:32:14.353 回答
0

我使用了 Boris Stitnicky 的算法并用 Java 编写了我的解决方案。但是我选择了逆时针方向，为了检查区间的哪一点是起点，哪一点是区间的终点，我使用了叉积。你可以在这里找到它：https ://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java

于 2015-01-26T05:51:29.523 回答