凸出的船體或給定的一組點與最低可能的周長

Question

給定n> = 3點在飛機上。 我們正在尋找符合這些條件的一個或兩個多邊形：

1. 從給定的設定點位於多邊形 或在這些多邊形中的至少一個的周邊的每一個點。
2. 每個多邊形的每個頂點都在給定點之一中。
3. 該多邊形不能有零區域。

計算找到的多邊形的總周長的最小可能值。

我沒有找到最低邊界的多邊形的問題，但我找不到有效的解決方案來找到兩個最低邊界的多邊形。 （對於n> = 300）

我需要一些提示或什麼，什麼可以幫助我弄清楚如何解決它。

Answer 1

第一步是計算凸包。假設你的凸包H上的點是p0，p1，p2，p3，...，pn，p0。讓我們假設最佳的對流文本外殼A和B包含這個列表中的子集pA和pB。然後pA和pB通過在兩點分裂H得到。

現在你可以看到，你可以在H上只拆分O（n^2）個點。

既然你不想要完整的答案，我會給你留下餘下的。