Отчеты о диапазоне

В вычислительной геометрии и баз данных теории запрос на отчет о диапазоне запрашивает список точек, соответствующих запросу. Запрос часто задается геометрической фигурой, содержащей все точки, которые должны совпадать, и называется диапазоном. Отчеты о диапазонах — это особый случай поиска по диапазону , при котором запросы могут возвращать другие виды совокупной информации о точках в диапазоне.

Запросы отчетов о диапазонах часто обрабатываются путем построения структуры данных из набора точек, которые могут эффективно отвечать на запросы. Поскольку размер выходных данных в худшем случае для запроса отчета о диапазоне, измеренный как функция размера набора данных n , может сам быть n , большая часть исследований структур данных отчетов о диапазоне исследовала алгоритмы, чувствительные к выходным данным , где анализируется время запроса. как с точки зрения n, так и с точки зрения количества сообщаемых точек (часто обозначаемого k ).

Например, для одномерных (числовых) данных с диапазонами запросов, которые являются интервалами , запросы отчетов по диапазонам могут обрабатываться путем сохранения данных в отсортированном массиве. С помощью этой структуры можно использовать двоичный поиск , чтобы найти точку, ближайшую к началу интервала запроса, а затем сканировать массив от этой точки вперед, чтобы получить список всех точек в интервале. Хранение этой структуры данных использует O ( n ) (линейное) пространство и обрабатывает запросы за время O (log n + k ) на каждый запрос.

Ссылки

• Агарвал, ПК ; Эриксон, Дж. (1999), «Поиск геометрического диапазона и его родственники» (PDF) , в Шазель, Бернар ; Гудман, Джейкоб ; Поллак, Ричард (ред.), Достижения в дискретной и вычислительной геометрии: материалы совместной летней исследовательской конференции AMS-IMS-SIAM 1996 г., Дискретная и вычислительная геометрия - десять лет спустя, 14-18 июля 1996 г., Колледж Маунт-Холиок , Современность Математика, вып. 223, Издательство Американского математического общества, стр. 1–56 .