Наименьшее поле с выравниванием по оси, содержащее точек

Входные данные: набор из точек в и целое число . $n$ $\mathbb{R}^3$ $k \le n$

Выход: наименьший ограничивающий прямоугольник, выровненный по оси объема, который содержит не менее из этих точек. $k$ $n$

Мне интересно, если какие-либо алгоритмы известны для этой проблемы. Лучшее, что я мог придумать, было время , примерно следующее: грубая сила по всем возможным верхним и нижним границам для двух из трех измерений; для каждого из этих возможности, можно решить соответствующую - мерный вариант задачи в времени с использованием алгоритма скользящего окна. $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
источник

Разве мы не можем вычислить таблицу размером для числа точек с ? Вычисление количества точек и объема может быть выполнено с постоянным числом операций, и мы можем использовать динамическое программирование с таблицей размера и должны иметь возможность получить алгоритм .

n^{3}

$n^3$

p

$p$

p . x < x, p . y < y, p . z < z

$p.x< x, p.y<y, p.z <z$

k n^{3}

$k n^3$

O (k n^{3})

$O(kn^3)$

Каве

Хорошо. В этом случае, что , вы не можете надеяться сделать лучше, чем . Потому что есть различных различных блоков, и путем усреднения аргумента (по случайному значению k) есть блоков, содержащих ровно k точек. Если вы не можете каким-то образом использовать объемную штуковину, чтобы каким-то образом уменьшить пространство поиска, но это как-то кажется оптимистичным ...

k = Θ (n)

$k=\Theta(n)$

n^{5}

$n^5$

n^{6}

$n^6$

n^{5}

$n^5$

Сариэль Хар-Пелед

Кстати, в вашем случае вы можете получить коробку, содержащую точек, которая меньше оптимальной ячейки, содержащей точек в время. Для это, по сути, время полилога., ..

(1 - ϵ) k

$(1-\epsilon)k$

k

$k$

O (((n / k) / ϵ^{2} \log n)^{O (1)})

$O( ((n/k)/\epsilon^2 \log n)^{O(1)})$

k = Θ (n)

$k = \Theta(n)$

Сариэль Хар-Пелед

Ответы:

Для точек есть пустых ящиков, см. Введение к этой статье http://www.cs.uwm.edu/faculty/ad/maximal.pdf . Можно вычислить эти блоки примерно за это время (см. Введение для ссылок). $n$ $O(n^3)$

Для вашей задачи возьмите случайную выборку точек, где каждая точка выбрана с портативностью . Такая случайная выборка имеет размер (в ожидании) [и ради противоречия предположим, что это так]. Имеется пустых ящиков с точками из на их сторонах, как указано выше. Для каждого такого блока используйте структуру данных поиска с ортогональным диапазоном, чтобы вычислить, сколько именно точек оно содержит. Повторите этот процесс раз. С большой вероятностью одна из пробных коробок является желаемой. $1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$

В целом, время выполнения этого . $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$

Чтобы понять, почему это работает, рассмотрим оптимальную коробку. На его границе 6 точек P. Вероятность того, что случайная выборка выберет эти шесть точек, и ни одна из точек внутри прямоугольника, равна по крайней мере . Таким образом, если вы повторите процесс раз, с высокой вероятностью одна из случайных выборок вызовет желаемое поле как пустое поле. $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$ $O( (1/p) \log n)$

Поскольку ограничено числом пустых ящиков (см. Введение в приведенной выше статье для соответствующих ссылок), маловероятно, что возможен значительно более быстрый алгоритм. $\Theta(n^3)$

[В ссылке, которую я дал, они упоминают, что [17] предоставляет алгоритм, который перечисляет все максимально пустые поля среди точки в 3d за времени, который является черным ящиком, который вам нужен для вышеупомянутого .] $O(n^3 \log^2 n)$

Сариэль Хар-Пелед
источник

Спасибо - это великолепно! Деталь, которую я действительно должен был упомянуть (извините!), Это то, что для моих целей, поэтому примерно так же хорош, как . Тем не менее, здесь есть много очень интересных идей, которые могут быть полезны для большой версии ...

k = Θ (n)

$k = \Theta(n)$

O (n^{3} k^{3})

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$

GMB