algorithm - ポリゴン構築の複雑さ

Question

与えられた点のセット (2D) から単純な多角形を構築する問題の複雑さが少なくともO(n logn)であることを証明したい。つまり、すべての正しいアルゴリズムは、これを解決するために少なくとも O(n logn) ステップを必要とする最悪の場合の問題。この問題を何らかの方法で並べ替えの問題に減らすことは可能ですか、またはこれをどのように示すことができますか?

Answer 1

はい、ベースライン アルゴリズムを使用します。

• x 値の最小値と最大値を持つ 2 つの点を見つける: O(n)
• ベースライン (これらのポイントを結ぶ線) の上下にある 2 つのセットに他のポイントを分割します: O(n)
• 上位セットを「昇順 y/昇順 x」でソート: O(n*logn)
• 下位セットを「降順 y/降順 x」でソート: O(n*logn)
• 上位集合を順に結合、下位集合を順に結合: O(n)

Answer 2

はい、並べ替えの問題と比較することで証明できますが、逆に減らす必要があります。つまり、ソートの問題を O(n) 時間でポリゴン構築の問題に減らします。