Выберите прямоугольники с максимальной площадью пересечения

Поскольку пересечение прямоугольников, выровненных по оси, является прямоугольником, выровненным по оси, существует O(N⁴) возможных пересечений (O(N) слева, O(N) справа, O(N) вершин, O(N) низов). Очевидный алгоритм O(N⁵) состоит в том, чтобы попробовать все из них, проверяя для каждого, содержится ли он хотя бы в N - r прямоугольниках.

Улучшение O(N³) состоит в том, чтобы попробовать все интервалы O(N²) в измерении X и запустить алгоритм 1D в измерении Y на тех прямоугольниках, которые содержат заданный X-интервал. (Прямоугольники нужно отсортировать только один раз.)

Насколько велико число N? Я ожидаю, что причудливые структуры данных могут привести к алгоритму O(N² log N), но это не будет стоить вашего времени, если будет достаточно кубического алгоритма.

Кажется, у меня есть контрпример. Допустим, у вас есть r := N-2. т.е. вы хотите найти два прямоугольника с максимальным перекрытием. Допустим, вам нужны прямоугольники, покрывающие одну и ту же площадь (= максимальное перекрытие). Эти два будут оптимальным результатом в конце.

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

Допустим, у нас есть три прямоугольника, которые сильно перекрываются... но они не оптимальны. Они имеют очень маленькую область перекрытия с двумя другими прямоугольниками.

Теперь, если вы хотите оптимизировать площадь для четырех прямоугольников, вы удалите один из двух оптимальных прямоугольников, верно? Или, может быть, вам НЕ НУЖНО, но вы не уверены, какое решение является оптимальным.

Итак, я думаю, что ваш алгоритм сокращения не совсем корректен. Atm Я не уверен, есть ли для этого хороший алгоритм или к какому классу сложности он принадлежит. Если у меня будет время, я подумаю об этом :)

Постскриптум. Это довольно ущербно, но может вызвать некоторые идеи. Это особенно плохо, когда в квадранте, расположенном рядом с осями X и Y, есть выбросы - они будут иметь тенденцию усиливать друг друга, как если бы они оба были под углом 45 градусов, отталкивая решение от этого квадранта таким образом, что это может не сделать. смысл.

-

Если r намного меньше, чем N, а N довольно велико, рассмотрите это:

Найдите средний центр.
Сортируйте прямоугольники в 2 последовательности (X – центр.x) + (Y – центр.y) и (X – центр.x) – (Y – центр.y), где X и Y — центр каждого прямоугольника.

Для любого решения все прямоугольники отклонения будут членами до 4 подпоследовательностей, каждая из которых является началом или хвостом каждой из 2 последовательностей. Предполагая, что N намного больше, чем r, большая часть времени будет занимать сортировку последовательностей - O (n log n).

Чтобы найти решение, сначала найдите пересечение, заданное удалением r прямоугольников в начале и в конце каждой последовательности. Используйте это базовое пересечение, чтобы не учитывать «основной» набор прямоугольников, который, как вы знаете, будет в решении. Это уменьшит вычисления пересечения до работы с прямоугольниками до 4 * r + 1.

Каждая из 4 головок и концов последовательности должна быть связана с массивом из r прямоугольников, каждая запись представляет собой пересечение, заданное пересечением «ядра» с i самыми внутренними прямоугольниками из головы или хвоста. Это предварительное вычисление снижает сложность поиска решения с O (r ^ 4) до O (r ^ 3).

Это не идеально, но должно быть близко.

Дефекты с малым r будут возникать из-за того, что должны быть отбракованы, которые находятся под разными углами, с альтернативами, которые немного лучше, но на одной из двух осей. Максимальная ошибка, вероятно, вычислима. Если это вызывает беспокойство, используйте вычисление реальной площади непересечения вместо простой формулы разности «X + Y», которую я использовал.

Вот явный контрпример (с N=4 и r=2) к жадному алгоритму, предложенному автором вопроса.

Максимальное пересечение между тремя из этих прямоугольников находится между черным, синим и зеленым прямоугольниками. Но ясно, что максимальное пересечение между любыми двумя из этих трех меньше, чем пересечение между черным и красным прямоугольниками.

Я все еще пытаюсь привыкнуть к этому сайту. Каким-то образом мой предыдущий ответ был сокращен до двух предложений. Спасибо всем за их вклад, особенно mhum, чей контрпример к жадному алгоритму удовлетворителен. Теперь у меня есть ответ на мой собственный вопрос. Я считаю, что это максимально возможно, но нижние границы сложности для меня слишком сложны. Мое решение похоже на решение Эда Стауба выше и дает те же оценки сложности, но работает для любого значения r > 0.

Один из моих прямоугольников определяется его нижним левым углом. Пусть S будет множеством нижних левых углов. За время O(N log(N)) мы сортируем S в Sx в соответствии с размерами координат x. Нас не волнует порядок внутри Sx между двумя нижними левыми углами с одной и той же координатой x. Точно так же отсортированная последовательность Sy определяется с использованием размеров y-координат. Пусть теперь u1, u2, u3 и u4 — целые неотрицательные числа, причем u1+u2+u3+u4=r. Мы вычисляем, что происходит с областью, когда мы удаляем различные прямоугольники, которым мы теперь дали явное имя. Сначала мы удаляем голову Sx размером u1 и хвост Sx размером u2. Пусть Syx будет результатом удаления этих записей u1+u2 из Sy. Мы удаляем голову Syx размером u3 и хвост Syx размером u4. Теперь можно доказать, что один из этих возможных вариантов (u1,u2,u3,u4) дает желаемую максимальную площадь пересечения. (Напишите мне, если вам нужен PDF-файл с деталями доказательства.) Количество таких вариантов равно количеству целых точек в правильном тетраэдре в 4-мерном евклидовом пространстве с вершинами в 4 точках, сумма координат которых равна r, и для какие 3 из 4 координат равны 0. Это ограничено объемом тетраэдра, что дает оценку сложности O (r ^ 3).

Таким образом, мой алгоритм имеет временную сложность O (N log (N)) + O (r ^ 3).

Я считаю, что это дает идеальное решение. Решение Дэвида легче реализовать, и в большинстве случаев оно должно работать быстрее.

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

Вычисление выпуклой оболочки. Соберите набор всех решений-кандидатов, созданных:

{Remove a hull member, repair the hull} r times

(Корпус действительно не нужно ремонтировать в последний раз.)

Если h - количество начальных элементов корпуса, то сложность меньше, чем h ^ r плюс стоимость вычисления начального корпуса. Я предполагаю, что алгоритм корпуса выбран таким образом, чтобы отсортированные данные можно было сохранить и повторно использовать при ремонте корпуса.

Это просто мысль, но если N очень велико, я бы, наверное, попробовал алгоритм Монте-Карло.

Идея состоит в том, чтобы генерировать случайные точки (скажем, равномерно в выпуклой оболочке всех прямоугольников) и оценивать, как работает каждая случайная точка. Если случайная точка находится в N-r или более прямоугольниках, обновите количество попаданий каждого подмножества из N-r прямоугольников.

В конце концов, вашим ответом будет N-r подмножество прямоугольников с наибольшим количеством случайных точек.

Этот алгоритм имеет много недостатков, наиболее очевидным из которых является то, что результат является случайным и, следовательно, не гарантируется его правильность. Но, как и большинство алгоритмов Монте-Карло, он хорошо масштабируется, и вы сможете использовать его и с более высокими измерениями.