Границы компромисса для подсчета диапазона полупространства

10

Какова текущая наилучшая граница для выполнения запросов подсчета диапазона полупространства для набора мерных точек, выраженного в форме компромисса времени / пространства. Согласно основополагающей работе Матусека 1993 года (теорема 6.2, Поиск диапазона с эффективными иерархическими вырезами), мы можем выполнять подсчет диапазона для запросов, которые являются пересечением полупространств, для , используя структуру данных размера , для , в время. Для это время . Тем не менее, исследование Agarwal по поиску дальности (Таблица 36.3.2) утверждает, что граница $d$ $p$ $1 \le p \le d+1$ $O(m)$ $n \le m \le n^d$ $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ $p=1$ $O(n/m^{1/d})$ $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$ . Какое правильное утверждение связано? Или что я недопонимаю? Наконец, есть ли скрытый лог-термин, когда ? $m=n^d$

reference-request ds.data-structures cg.comp-geom ПКН
источник

6

Более строгие сроки Матушека верны.

В доказательстве теоремы 6.1 ( в журнальной версии ) используется трюк с косвенным обращением, который уменьшает ограничение пространства, необходимое для логарифмического времени запроса, с до . Интуитивно понятно, что задача состоит в том, чтобы сгруппировать точки в подмножества полилогарифмического размера, построить структуру данных линейного пространства для каждого подмножества, а затем построить стандартную логарифмическую структуру времени запроса по подмножествам. Включение улучшенного пространства, связанного с многоуровневым / компромиссным механизмом Матушека, который описан в общем виде в более длинной версии опроса Агарвала, дает Матушеку форму пространственно-временного компромисса. (На самом деле, трюк косвенного действия - это просто очень осторожное применение стандартного компромиссного механизма.) $O(n^d)$ $O(n^d/\operatorname{polylog} n)$

Jeffε
источник

Просто чтобы быть точным: теорема 6.2 в статье Матоусека утверждает, что подсчет полупространства может быть сделан в пространстве, времени. При , это времени ... нет неустановленного фактора аддитивной журнала? Я спрашиваю только потому, что в обзоре теорема 7 и следствие 8 имеют добавку , которой нет в формулировке теоремы Матусека.

O (m)

$O(m)$

O (n / m^{1 / d})

$O(n/m^{1/d})$

m = n^{d}

$m = n^d$

O (1)

$O(1)$

O (l o g (m / n))

$O(log (m/n))$

ркн

Ах я вижу. Да, есть ошибка; верхняя граница в формулировке теоремы слишком свободна. Для доказательства требуется ; в противном случае целочисленный параметр будет меньше . Добавление логарифмического термина ко времени запроса также устраняет проблему.

m \leq n^{d}

$m \le n^d$

m = O (n^{d} / \log^{d - p + 1} n)

$m = O(n^d / \log^{d-p+1} n)$

r

$r$

1

$1$

Джеффс

2

Существует краткое обсуждение результатов поиска в полупространстве чуть выше таблицы 36.3.2 в Обзоре Агарвала и другого в разделе 4.3 этого опроса . Первый, похоже, не дает много подробностей, кроме того, что «компромисс между пространством и запросом для поиска в симплексном диапазоне может быть достигнут путем объединения линейных и логарифмических структур данных времени запроса», но последний, по-видимому, дает немало подробнее о компромиссе между пространством и запросом. Я предлагаю рассмотреть раздел 4.3, теорему 7, следствие 8 и их доказательства. Я не прочитал их достаточно подробно, чтобы знать, отвечает ли он полностью на ваш вопрос, но это, по крайней мере, хорошее место для начала.

Джо
источник

Границы компромисса для подсчета диапазона полупространства

Ответы: