範囲検索

コンピュータサイエンスにおいて、範囲検索問題は、オブジェクトのセットS を処理して、 Sのどのオブジェクトが範囲と呼ばれるクエリオブジェクトと交差するかを判断することから構成されます。たとえば、Sがいくつかの都市の座標に対応するポイントの集合である場合、指定された緯度と経度の範囲内の都市のサブセットを見つけます。

範囲探索問題とそれを解くデータ構造は、計算幾何学の基本的なテーマです。この問題は、地理情報システム(GIS)、コンピュータ支援設計(CAD)、データベースなどの分野で応用されています。

この問題にはいくつかのバリエーションがあり、バリエーションによって異なるデータ構造が必要になる場合があります。^[1]効率的な解決策を得るためには、問題のいくつかの側面を指定する必要があります。

• オブジェクトの種類: アルゴリズムは、 S がポイント、線、線分、ボックス、ポリゴンなどから構成されているかどうかによって異なります。検索する最も単純で最も研究されているオブジェクトはポイントです。
• 範囲の種類: クエリ範囲も、事前に決定されたセットから抽出する必要があります。よく研究されている範囲のセットと、それぞれの問題の名前は、軸に沿った長方形(直交範囲検索)、単体、半空間、球/円です。
• クエリの種類: クエリ範囲と交差するすべてのオブジェクトのリストを報告する必要がある場合は、問題は範囲報告と呼ばれ、クエリは報告クエリと呼ばれます。範囲と交差するオブジェクトの数だけが必要な場合もあります。この場合、問題は範囲カウントと呼ばれ、クエリはカウントクエリと呼ばれます。空クエリは、範囲と交差するオブジェクトが少なくとも 1 つあるかどうかを報告します。セミグループ バージョンでは、可換 セミグループ( S 、+) が指定され、各ポイントにSからの重みが割り当てられ、範囲と交差するポイントの重みのセミグループの合計を報告する必要があります。
• 動的範囲検索と静的範囲検索: 静的設定では、セットS は事前にわかっています。動的設定では、クエリ間でオブジェクトが挿入または削除される可能性があります。
• オフライン範囲検索: オブジェクトのセットとクエリのセット全体の両方が事前にわかっています。

直交範囲検索では、集合S は次元の点から構成され、クエリは各次元の区間から構成されます。したがって、クエリは多次元の軸に沿った長方形で構成されます。出力サイズ で、Jon Bentley はkd ツリーを使用して( Big O 表記法で)空間とクエリ時間を実現しました。^{[2] Bentley は}範囲ツリーの使用も提案しました。これにより、クエリ時間は まで短縮されますが、空間は まで増加します。^[3] Dan Willard は、分数カスケードの特殊なケースであるダウンポインターを使用して、クエリ時間をさらに まで短縮しました。^[4]${\displaystyle n}$${\displaystyle d}$${\displaystyle k}$${\displaystyle O(n)}$${\displaystyle O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}}$${\displaystyle O(\log^{d}n+k)}$${\displaystyle O(n\log^{d-1}n)}$ ${\displaystyle O(\log^{d-1}n+k)}$

上記の結果はポインタマシンモデルで達成されましたが、低次元（2D、3D、4D）での計算のワードRAMモデルではさらなる改善が行われました。 バーナード・チャゼルは、範囲カウントのクエリ時間とスペースを達成するために圧縮範囲木を使用しました。 ^[5]ジョセフ・ジャジャと他の人たちは、その後、範囲カウントのこのクエリ時間を に改善しました。これは下限と一致し、したがって漸近的に最適です。^[6]${\displaystyle O(\log n)}$${\displaystyle O(n)}$${\displaystyle O\left({\dfrac {\log n}{\log \log n}}\right)}$

2015年現在、Timothy M. Chan、Kasper Larsen、Mihai Pătrașcuによって発見された、圧縮された範囲木を計算のワードRAMモデルで使用した範囲報告の最良の結果（低次元（2D、3D、4D））は、次のいずれかです。^[7]

• ${\displaystyle O(n)}$スペース、クエリ時間${\displaystyle O(\log ^{\epsilon }n+k\log ^{\epsilon }n)}$
• ${\displaystyle O(n\log \log n)}$スペース、クエリ時間${\displaystyle O(\log \log n+k\log \log n)}$
• ${\displaystyle O(n\log ^{\epsilon }n)}$スペース、クエリ時間${\displaystyle O(\log \log n+k)}$

直交の場合、境界の 1 つが無限大であれば、クエリは 3 辺型と呼ばれます。境界の 2 つが無限大であれば、クエリは 2 辺型であり、境界のいずれも無限大でない場合は、クエリは 4 辺型です。

静的範囲検索では集合S が事前に分かっているのに対し、動的範囲検索では点の挿入と削除が許可されます。増分バージョンの問題では挿入のみが許可され、減分バージョンでは削除のみが許可されます。直交ケースでは、Kurt Mehlhornと Stefan Näher が動的範囲検索のデータ構造を作成しました。これは、動的分数カスケーディングを使用して空間とクエリ時間を実現します。^[8]増分バージョンと減分バージョンの両方の問題はクエリ時間で解決できますが、一般的な動的範囲検索がそのクエリ時間で実行できるかどうかは不明です。 ${\displaystyle O(n\log n)}$${\displaystyle O(\log n\log \log n+k)}$${\displaystyle O(\log n+k)}$

色範囲カウントの問題は、点がカテゴリ属性を持つ場合を考慮します。カテゴリが幾何学的空間内の点の色と見なされる場合、クエリは特定の範囲に何色の色が表示されるかです。Prosenjit Gupta らは 1995 年に、空間とクエリ時間における 2D 直交色範囲カウントを解決するデータ構造を説明しました。^[9]${\displaystyle O(n^{2}\log^{2}n)}$${\displaystyle O(\log^{2}n)}$

範囲検索、特に直交範囲検索は、計算幾何学で考慮されるだけでなく、データベースの範囲クエリにも応用できます。色付き範囲検索は、カテゴリ データの検索にも使用され、カテゴリ データの検索が目的です。たとえば、年齢が 25 歳から 40 歳で、資産が 10,000 ドルから 20,000 ドルの人々を表す銀行口座のデータベースの行を特定することは、年齢と金額が 2 つの次元である直交範囲レポートの問題である可能性があります。

• レンジツリー
• 範囲クエリ

• デ・バーグ、マーク。マーク・ヴァン・クレフェルト。マーク・オーヴァーマーズ; Schwarzkopf、Otfried (2000)、Computational Geometry (第 2 版)、ベルリン: Springer-Verlag、ISBN 3-540-65620-0
• Matoušek、Jiří (1994)、「幾何学的範囲検索」、ACM Computing Surveys、26 (4): 421–461、doi :10.1145/197405.197408、S2CID  17729301。