10

ここに興味深い演習があります：

P を単純であるが必ずしも凸であるとは限らない多角形とし、q を P 内にあるとは限らない任意の点とします。

P のエッジの最大数と交差する q から始まる線分を見つける効率的なアルゴリズムを設計してください。

言い換えれば、点 q に立っている場合、弾丸が最も多くの壁を通過するには、銃をどの方向に向ければよいでしょうか?

P の頂点を通過する弾丸は、1 つの壁に対してのみクレジットを取得します。

O(n log n) アルゴリズムが可能です。n は頂点またはエッジの数です。これはポリゴンであるため、エッジの数は頂点の数にほぼ等しくなります。

ここに私の考えがあります：

最初に P のすべての頂点 (N 個の頂点があるとしましょう) と q を接続します。N 行、または N-1 対の行があります。

最後の射撃ラインは、これらのペアの間にある必要があります。したがって、最大数のエッジを含むペアを見つける必要があります。

この解決策は O(n log n) ではないと思います。

何か案は？

4

2 に答える 2

10

まず、点の座標を P を中心とする極座標系に変換します。

  • 一般性を失うことなく、角度座標に関して時計回りの方向を特別なものとして選択しましょう。
  • 次に、多角形のすべてのエッジに沿って順番に円形のウォークを実行してみましょう。これらのエッジの開始点と終了点に注目してください。ウォークは、P に対して時計回りの方向に進みます。
  • このようなエッジの終点を「尻」、始点を「頭」と呼びましょう。これはすべて O(n) で行う必要があります。次に、これらの頭と尻を並べ替える必要があるため、クイックソートを使用するとO(nlog(n)). 最小の φ から角度 (φ) 座標で並べ替え、φ 座標が等しい場合、頭が尻よりも小さいと見なされるようにします (これは、問題の最後の規則に準拠するために重要です)。
  • 終了したら、最小の φ からそれらを歩き始め、バットに遭遇するたびに実行中の合計を増やし、頭に遭遇するたびに減らし、φ 座標上の間隔であるグローバル最大値に注目します。これも O(n) で行う必要があるため、全体的な複雑さはO(nlog(n))です。

では、なぜこのような質問をするのか教えてください。

于 2012-05-06T21:32:14.353 に答える
0

Boris Stitnicky のアルゴリズムを使用し、Java でソリューションを作成しました。しかし、私は反時計回りの方向を選択し、間隔のどの点が開始点であり、どの点が間隔の終わりであるかを確認するために、外積を使用しました。ここで見つけることができます: https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java

于 2015-01-26T05:51:29.523 に答える