範囲報告

計算幾何学およびデータベース理論において、範囲レポートクエリは、クエリに一致する点のリストを要求するものです。クエリは多くの場合、一致するはずのすべての点を含む幾何学的形状によって指定され、これを範囲と呼びます。範囲レポートは範囲検索の特殊なケースであり、クエリは範囲内の点に関する他の種類の集計情報を返すことがあります。

範囲報告クエリは、クエリに効率的に応答できる点の集合からデータ構造を構築することによって処理されることが多い。範囲報告クエリの最悪ケースの出力サイズは、データセットのサイズnの関数として測定するとn自体になる可能性があるため、範囲報告データ構造に関する研究の多くは、出力に敏感なアルゴリズムを調査しており、クエリ時間はnと報告された点の数 (多くの場合kで表される) の両方の観点から分析される。

例えば、クエリ範囲が区間である一次元（数値）データの場合、範囲レポートクエリは、データをソート済み配列に格納することで処理できます。この構造では、バイナリサーチを使用してクエリ区間の開始点に最も近い点を見つけ、その点から配列を走査して区間内のすべての点をリストできます。このデータ構造を格納するにはO ( n )（線形）の空間が必要となり、クエリ1件あたりの処理時間はO (log n + k )となります。

• Agarwal, PK ; Erickson, J. (1999)、「幾何学的範囲探索とその関連手法」(PDF)、Chazelle, Bernard ; Goodman, Jacob ; Pollack, Richard (編)、「離散幾何学と計算幾何学の進歩：1996年AMS-IMS-SIAM合同夏季研究会議『離散幾何学と計算幾何学―10年後』、1996年7月14日～18日、マウント・ホリヨーク大学」、Contemporary Mathematics、第223巻 、American Mathematical Society Press、pp. 1–56 、 2011年6月29日にオリジナル(PDF)からアーカイブ、 2016年12月18日に取得 。