16

给定平面上的 n 个点。No 3 是共线的。

给定数字 k。

找到 k 点的子集，使得 k 点的凸包在 k 点子集的任何凸包中具有最小周长。

我可以想到一个天真的方法在 O(n^kk log k) 中运行。（找到每个大小为 k 的子集的凸包并输出最小值）。

我认为这是一个 NP 问题，但我找不到任何适合归约的东西。

有人对这个问题有想法吗？

一个例子，

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

结果：

{(0,0),(0,1),(1,0)}

由于该集合包含 3 个点，因此结果的凸包和周长小于任何其他 3 个点的集合。

4

4 回答 4

9

这可以在 O(kn^3) 时间和 O(kn^2) 空间中完成（或者如果您想要实际点，也可以在 O(kn^3) 中完成）。

本文： http: //www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf

Eppstein 等人的算法可以解决最小周长和其他权重函数（如面积、内角总和等）的问题，这些函数遵循一定的约束，即使标题说的是最小面积（周长参见推论 5.3）。

基本思想是如下动态规划方法（阅读第 4 节的前几段）：

假设 S 是给定的点集，Q 是具有最小周长的 k 个点的凸包。

设 p1 是 Q 的最底部点，p2 和 p3 是船体上按逆时针顺序排列的下一个点。

我们可以将 Q 分解为一个三角形 p1p2p3 和一个由 k-1 个点 Q' 组成的凸包（它与三角形 p1p2p3 共享边 p1p3）。

主要观察结果是 Q' 是 k-1 的最优值，其中最底部的点是 p1，下一个点是 p3，并且 Q' 的所有点都位于线 p2->p3 的同一侧。

因此为每个四元组 (pi, pj, pk, m) 维护一个 4d 最佳多边形数组，使得

  • 多边形是 S 中恰好 m 个点的凸包。
  • pi 是多边形的最底点。
  • pj 是逆时针顺序的下一个顶点，
  • 多边形的所有点都位于线 pi -> pj 的左侧。
  • 所有点都与 pi 一样位于 pj->pk 的同一侧。

可以帮助我们找到 m=k 的最佳多边形，给定 m <= k-1 的最佳多边形。

该论文准确地描述了如何去做，以实现规定的空间和时间界限。

希望有帮助。

于 2010-06-22T06:02:00.217 回答
2

这不是一个很好的解决方案。事实上，实现起来相当痛苦，但它肯定会产生多项式复杂性。虽然复杂性也很大（n^5*k 是我的粗略估计），但有人可能会找到改进它的方法或在这里找到更好解决方案的想法。或者它可能对你来说就足够了：即使这种复杂性也比蛮力好得多。

注意S：带外壳的最优解（集合）H包括内部原始集合的所有点H。否则，我们可以丢弃其中一个边界点H并包括该错过的点，从而减少周长。
（更新就像发布的“优化” mbeckish）

假设：集合中没有两点形成一条垂直线。它可以通过围绕坐标原点将整组点旋转一些不合理的角度来轻松实现。

由于上述假设，任何复杂的船体都有一个最左边和一个最右边的点。此外，这两点将船体分为top和bottom部分。

现在，让我们从top这个船体的一部分中取出一个片段，并从该部分中取出一个片段bottom。让我们将这两个部分middle segments和这个船体右侧部分的周长称为right周长。
注意：这两个部分是我们需要了解的关于凸包右侧部分的所有信息，以便继续将其构建到左侧。但是只有两点而不是四点是不够的：我们不能以这种方式维持“凸”的条件。

它导致了一个解决方案。对于每组点 {p0, p1, p2, p3} 和数字i(i <= k)，我们存储如果 [p0, p1], [p2, p3] 是两个线段right可以达到的最小周长，并且是此解决方案部分中的点（包括其中的点，不仅在边界上）。middleiright

我们从右到左遍历所有点。对于每个新点p，我们检查点 {p0, p1, p2, p3} 的所有组合，以便点 p 可以将这个外壳继续向左（在该部分上top或在该bottom部分上）。对于每个这样的 set 和 size i，我们已经存储了最佳周长尺寸（参见上面的段落）。

注意：如果您将点添加p到right-hull由点 {p0, p1, p2, p3} 形成的点，您将i至少将集合大小增加 1。但有时这个数字将 > 1：您必须包括所有点三角形 {p, p0, p2}。它们不在船体上，而是在船体内。

算法结束 :) 此外，尽管复杂性令人恐惧，但您可能会注意到并非所有段 [p0, p1], [p2, p3] 都可以是middle段：它应该会大大减少实际计算时间。

更新这仅提供最佳周长大小，而不是集合本身。但是找到集合很简单：对于上面的每个“状态”，您不仅存储周长大小，还存储最后添加的点。然后，您可以“追溯”您的解决方案。这是相当标准的把戏，我想这对你来说不是问题，你似乎擅长算法:)

update2 这个本质上是DP（动态编程），只是有点臃肿

于 2010-06-21T19:58:48.133 回答
1

一种可能的优化：您可以忽略其凸包包含不在子集中的点的任何子集。

证明：

如果您的凸包包含不在您的子集中的点，则从您的子集中删除一个位于外壳上的点，并将其替换为外壳内部的一个点。这将产生一个相等或更小的周长的船体。

于 2010-06-21T19:35:38.940 回答
-2

在平面情况下，您可以使用称为 Jarvis March 的算法，它的最坏情况复杂度为 O(n^2)。在此算法中，您开始在任意点构建船体，然后检查接下来需要添加哪个点。伪代码取自维基百科：

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]         // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0]      // wrapped around to first hull point

据我了解，凸包对于每组点都是唯一的，因此无需找到最小值。你只要找到一个，它就会是定义上最小的一个。

编辑

发布的解决方案解决了具有最少点数的凸包。任何具有更多点的船体将具有更长的周长，我误解了寻求最小周长的问题，而不是具有 K 点的集合的最小周长。

这个新问题很可能被怀疑为 NP，并且与最长路径问题最相似。不幸的是，我缺乏提供有价值的减少的独创性。

于 2010-06-21T18:41:05.123 回答