長方形のセットがあるとします (寸法が異なるか同じ)。
- タスクは、指定された長方形以上の長方形をセットから見つける (そして削除する) ことです。
- また、指定された四角形を取り囲むことができるセット内の最小の四角形である必要があります。
これは、線形検索/更新を行うことで O(n) 時間で簡単に解決できますが、より良い結果を達成することは可能ですか? O(log n) が最適だと思います。私の場合、これを使用するには、挿入と削除も O(n) よりも高速でなければなりません。
最適な四角形を見つけるのではなく、2 番目の制限を緩和してショートカットを作成することはできますか。
Zオーダー曲線（幅/高さ）を使用し、1次元インデックスとして使用して、それをツリーと組み合わせるという方針に沿って考えていました。それはうまくいくでしょうか？それとも無駄が多いのでしょうか？
もう 1 つの方法は、1 つの軸を使用してツリーを使用し、もう 1 つの軸を直線的にテストすることです。
誰かが似たようなことをして、その経験を共有できますか?