点集子集的最小周长凸包

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

Eppstein等人提出了一种算法来解决最小周长和其他权重函数(如面积、内角总和等)的问题,这些函数遵循一定的约束条件,尽管标题中说的是最小面积(周长见推论5.3)。

设S是给定的点集,Q是k点的最小周长凸包。

我们可以将Q分解为一个三角形p1p2p3和一个k-1点Q'(与三角形p1p2p3共用边p1p3)的凸壳。

因此,为每四个(pi,pj,pk,m)保持最佳多边形的4d阵列,使得

• pi是多边形的最底端点。
• 多边形的所有点都位于直线pi的左侧->睡衣。
• 所有点位于pj的同一侧->pk和pi一样。

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

希望有帮助。

这可不是什么好办法。事实上,这是一个相当痛苦的实现,但它肯定会给多项式的复杂性。虽然复杂性也很大(我粗略估计是n5*k),但有人可能会找到改进的方法,或者在这里找到更好的解决方案。或者对你来说已经足够了:即使是这种复杂性也比暴力强得多。

注意 :最优解(集 S H 包括原始集合内部的所有点 H . 否则,我们就可以扔掉 包括漏点,减少周长。
( 更新 就像“优化” 姆贝基什

:集合中没有两个点形成垂直线。它可以很容易地实现旋转的一些无理角度周围的坐标原点整组点。

top 和 bottom 部分。

顶部 一部分是船体另一部分是 部分。我们把这两部分称为 middle segments 以及船体右侧的周长- right
注意 :这两部分是我们需要知道的关于凸包的右侧部分的所有信息,以便继续在左侧构建凸包。但只有两点而不是四点是不够的:我们不能这样维持“凸”的条件。

. 对于每一组点{p0,p1,p2,p3}和数字 i (i<=k) 我们存储最小 正确的 如果[p0,p1],[p2,p3]为2,则可获得的周长 middle 分段和 我 是中的点数 正确的 此解决方案的一部分(包括其中的解决方案,而不仅仅是边界上的解决方案)。

我们从右到左遍历所有点。对于每个新点 p 顶部 或者在 底部 零件)。对于每一个这样的集合和大小 我 ,我们已经存储了最佳周长大小(参见上面的段落)。

注意 p 到 right-hull 由点{p0,p1,p2,p3}构成,您将增加集合大小 我

算法结束了:)此外,尽管复杂程度令人恐惧,但您可能会注意到,并非所有的段[p0,p1],[p2,p3]都可以 中间的

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

这本质上是DP(动态规划),只是有点臃肿

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

证明:

wikipedia

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点的集合的最小周长。