algorithm - 点集子集的最小周长凸包

Question

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

给定数字 k。

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

我能想到一个天真的方法在 O(n^k k 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 点集合。

Answer 1

这可以在 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 的最佳多边形。

这篇论文准确地描述了如何去做才能达到规定的空间和时间范围。

希望对您有所帮助。