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 上的点。

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