4

平面上に一連の点があり、それぞれが整数座標のペアで記述されていると想像してみましょう。O（n ^ 3）アルゴリズムよりも速く、可能な限り最大の面積を持つこの点に頂点を持つ三角形を見つける方法はありますか?

4

1 に答える 1

1
  1. 凸包を見つけます。
  2. 凸包上にある点 (A, B) の各ペアについて、三角形 ABC に最大面積を与える 3 番目の点 C を見つけます。これは、O(log n) のバイナリ検索を使用して実行できます。

二分探索を行うには、凸包上の点をある順序 (反時計回りなど) に配置します。A と B の間には 2 つの一連の点があり、1 つは A から B に、もう 1 つは B から A に向かいます。それぞれを別々に考えます。

二分探索の手順は以下の通りです。点の間隔の中央にある 3 つの連続した点 C、C'、C'' を取ります。3 つの領域 CAB、C'AB、C''AB を計算します。C' が 3 つの中で最大の場合、それはグローバルな最大値であり、検索は終了します。C が最大の場合、最大値は区間の左半分にあります。C'' が最大の場合、最大は右半分にあります。(編集: 新しい間隔には、端の 1 つに C' が含まれている必要があることに注意してください)。

そこに、O(n^2 log n) で動作するアルゴリズムがあります。

編集 2 :この質問への回答は、大幅に高速化する方法を示しています。両方のアプローチを組み合わせて、より良い結果を得ることができます (凸包が構築された後は O(log n) になりますが、船体の構築ではまだ O(n log n) です)。

于 2013-11-09T14:42:10.660 に答える