algorithm - 与えられたポイント セットの凸包または 2 つの凸包で、周囲が可能な限り小さいもの

Question

平面上の n>=3 点を指定します。これらの条件を満たす 1 つまたは 2 つのポリゴンを探しています。

1. 指定されたポイント セットのすべてのポイントは、ポリゴン内またはそれらのポリゴンの少なくとも 1 つの周囲に配置されます。
2. すべてのポリゴンのすべての頂点は、指定されたポイントの 1 つにあります。
3. ポリゴンの面積をゼロにすることはできません。

見つかったポリゴンの総周長の最小値を計算します。

周囲が最小のポリゴンを見つけることには問題はありませんが、周囲が最小の 2 つのポリゴンを見つけるための効果的な解決策が見つかりません。(n>=300 の場合)

ヒントか何かが必要です。解決方法を理解するのに何が役立つでしょうか。

Answer 1

最初のステップは、凸包を計算することです。凸包 H 上のポイントが p0、p1、p2、p3、...、pn、p0 であると仮定します。最適な凸包 A および B が、このリストのサブセット pA および pB を含むと仮定します。次に、H を 2 点で分割して pA と pB を求めます。

これで、H のみ O(n^2) 通りにポイントを分割できることがわかります。

あなたは完全な答えを望んでいないので、残りはあなたに任せます。