algorithm - 具有最小周长的给定点集的凸包或两个凸包

Question

给定平面上的 n>=3 个点。我们正在寻找满足这些条件的一两个多边形：

1. 给定点集的每个点都位于多边形中或至少位于其中一个多边形的周长处。
2. 每个多边形的每个顶点都在给定点之一中。
3. 多边形的面积不能为零。

计算找到的多边形的总周长的最小可能值。

我没有找到周长最短的多边形的问题，但我找不到任何有效的解决方案来找到两个周长最短的多边形。（对于 n>=300）

我需要一些提示或其他东西，什么可以帮助我弄清楚如何解决它。

Answer 1

第一步是计算凸包。假设凸包 H 上的点是 p0、p1、p2、p3、...、pn、p0。让我们假设最优凸包 A 和 B 包含来自该列表的子集 pA 和 pB。然后通过在两点处拆分 H 来获得 pA 和 pB。

现在您可以看到您只能在 O(n^2) 方式上拆分 H 点。

既然你不想要完整的答案，我就把休息留给你。