给出飞机上的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个点的周长.