Отчетность по дальности - Википедия - Range reporting

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

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

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

Рекомендации

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