基本的に、私が解決したい問題の定式化は非常に単純です。2 つの単純なポリゴン (自己交差なし) が与えられた場合、交差するすべてのエッジ ペアをO(n+k)時間で報告します。ここで、n はエッジの総数、k は 2 つのポリゴン間の交差の数です。
言及された時間の硬さの範囲内にとどまることが非常に重要です。このテーマに関する情報がほとんど見つからなかったことに、私は驚いています。ポリゴンの交差は、自然で重要な問題のようです。とにかく、現時点では、 O(n+k)でそれが可能かどうかはわかりません。
この問題の下限について誰か助けてもらえますか?