Cha*_* Xu 16 algorithm convex-hull computational-geometry
给出飞机上的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个点的周长.
小智 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最佳多边形阵列,使得
在给定m <= k-1的最佳多边形的情况下,可以帮助我们找到m = k的最佳多边形.
本文详细描述了如何实现这一目标,以达到规定的时空范围.
希望有所帮助.