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

11

Входные данные: набор из точек в и целое число .nR3kn

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

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

GMB
источник
Разве мы не можем вычислить таблицу размером для числа точек с ? Вычисление количества точек и объема может быть выполнено с постоянным числом операций, и мы можем использовать динамическое программирование с таблицей размера и должны иметь возможность получить алгоритм . p p . х < х , с . у < у , с . z < z k n 3 O ( k n 3 )n3pp.x<x,p.y<y,p.z<zkn3O(kn3)
Каве
Хорошо. В этом случае, что , вы не можете надеяться сделать лучше, чем . Потому что есть различных различных блоков, и путем усреднения аргумента (по случайному значению k) есть блоков, содержащих ровно k точек. Если вы не можете каким-то образом использовать объемную штуковину, чтобы каким-то образом уменьшить пространство поиска, но это как-то кажется оптимистичным ...n 5 n 6 n 5k=Θ(n)n5n6n5
Сариэль Хар-Пелед
Кстати, в вашем случае вы можете получить коробку, содержащую точек, которая меньше оптимальной ячейки, содержащей точек в время. Для это, по сути, время полилога., ..(1ϵ)kkO(((n/k)/ϵ2logn)O(1))k=Θ(n)
Сариэль Хар-Пелед

Ответы:

11

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

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

В целом, время выполнения этого .O((n/k)3k6polylogn)=O(n3k3logO(1)n)

Чтобы понять, почему это работает, рассмотрим оптимальную коробку. На его границе 6 точек P. Вероятность того, что случайная выборка выберет эти шесть точек, и ни одна из точек внутри прямоугольника, равна по крайней мере . Таким образом, если вы повторите процесс раз, с высокой вероятностью одна из случайных выборок вызовет желаемое поле как пустое поле.1k6(11/k)k61/k6=pO((1/p)logn)

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

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

Сариэль Хар-Пелед
источник
Спасибо - это великолепно! Деталь, которую я действительно должен был упомянуть (извините!), Это то, что для моих целей, поэтому примерно так же хорош, как . Тем не менее, здесь есть много очень интересных идей, которые могут быть полезны для большой версии ...O ( n 3 k 3 ) O ( n 6 ) kk=Θ(n)O(n3k3)O(n6)k
GMB