Найдите прямоугольник с наименьшей областью, которая может содержать другой прямоугольник

Question

Предположим, у меня есть набор прямоугольников (с разными или одинаковыми размерами).

1. Задача состоит в том, чтобы найти (и удалить) прямоугольник из набора, который больше или равен данному прямоугольнику.
2. Он также должен быть наименьшим прямоугольником в наборе, который может охватывать данный прямоугольник.

Это легко решается за O(n) время с помощью линейного поиска / обновления, но возможно ли достичь лучших результатов? O(log n) было бы оптимальным, я бы предположил. Вставка и удаление также должны быть быстрее, чем O(n), чтобы это пригодилось в моем случае.

Можно ли сделать какие-либо сокращения, не найдя оптимальный прямоугольник, а ослабьте 2-е ограничение: "Это также должен быть один из самых маленьких прямоугольников, который может охватывать данный прямоугольник"-

Я думал о том, чтобы использовать кривую Z-порядка (ширины / высоты) и использовать в качестве одномерного индекса и объединить его с деревом. Будет ли это работать? Или будет слишком много отходов?

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

Кто-нибудь делал что-то подобное и может поделиться своим опытом?

Answer 1

Вот идея, которая еще не полностью разработана:

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

Один узел (w, h) имеет 4 дочерних узла:

• (<w, <h) - содержит выступы, которые имеют меньшую ширину и меньшую высоту
• (>=w, <h) - содержит выступы, которые имеют большую ширину и меньшую высоту
• (<w, >=h) - содержит выступы, которые имеют меньшую ширину и большую высоту
• (>=w, >=h) - содержит выступы, которые имеют большую ширину и большую высоту

Когда вы спускаетесь в (w, h) Прямоугольный узел, чтобы искать контейнер для вашего (w2, h2) Прямо сейчас есть 4 разных случая:

• w2<w and h2<h - три варианта: (>=w, <h), (<w, >=h), (>=w, >=h)
• w2>=w and h2<h - два варианта: (>=w, <h), (>=w, >=h)
• w2<w and h2>=h - два варианта: (<w, >=h), (>=w, >=h)
• w2>=w and h2>=h - один вариант: (>=w, >=h)

Вам придется спуститься во все возможные ветви, что все же лучше, чем O(n).

Вставка - это O(log n). Не уверен насчет удаления и балансировки. Но я почти уверен, что есть решение и для этого.