Задача о наибольшем пустом прямоугольнике

Наибольшие пустые прямоугольники (зелёные) с различными ограничивающими объектами (с чёрными краями) . Светло-зелёный прямоугольник является подоптимальным (не максимальным) решением. Примеры A-C имеют стороны, параллельные осям, то есть сторонам светло-голубого фонового прямоугольника. Пример E показывает вариант задачи с произвольной ориентацией

Задача о наибольшем пустом прямоугольнике или задача о максимальном пустом прямоугольнике — это задача поиска прямоугольника максимального размера, который следует разместить среди препятствий на плоскости. Существует несколько вариантов задачи, в зависимости от особенностей формулировки, в частности, от способов измерения «размера», области (типы препятствий) и ориентации прямоугольника.

Задачи такого вида возникают, например, задачах в автоматизации проектирования электроники, в разработке и проверке компоновки интегральных схем.

Максимальный пустой прямоугольник (МПП) — это прямоугольник, который не содержит другой пустой прямоугольник. Каждая сторона МПП граничит с препятствием (в противном случае сторону можно было бы сдвинуть, увеличивая пустой прямоугольник). Приложение такого рода задач — перечисление «максимальных белых прямоугольников» в сегментации изображений при обработке изображений и распознавании образов. В контексте многих алгоритмов поиска наибольших пустых прямоугольников «максимальные пустые прямоугольники» являются кандидатами в решение, поскольку легко показать, например, что пустой прямоугольник наибольшей площади является максимальным пустым прямоугольником.

Классификация

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

Другая важная классификация — накладывается ли условие параллельности сторон осям, или стороны могут быть расположены произвольно.

Специальные случаи

Квадрат максимальной площади

Случай, когда искомый прямоугольник является квадратом со сторонами, параллельными осям, может быть рассмотрен с использованием диаграммы Вороного с метрикой $L_{1}$ для соответствующего множества препятствий, аналогично задаче о наибольшей пустой сфере. В частности, в случае точек внутри прямоугольника известен оптимальный алгоритм с временной сложностью $\Theta (n\log n)$.

Область: прямоугольник, содержащий точки

Задача, которую обсуждали Наамад, Ли и Шу в 1983, ставилась следующим образом: если дан прямоугольник A, содержащий n точек, нужно найти прямоугольник наибольшей площади, стороны которого параллельны прямоугольнику A, лежащий в прямоугольнике A и не содержащий какую-либо из данных точек. Наамад, Ли и Шу представили алгоритм с временной сложностью $O(\min(n^{2},s\log n))$, где s — число допустимых решений, т.е. максимальных пустых прямоугольников. Они также доказали, что $s=O(n^{2})$ и дали пример, в котором s квадратично зависит от n. Позднее появились статьи, представляющие более совершенные алгоритмы для задачи.

Область: препятствия в виде отрезков

Задачу поиска пустых изотетных прямоугольников среди изотетных отрезков первым рассматривали Нарди и Бхаттачарья в 1990. Позднее была рассмотрена более общая задача поиска пустых изотетных прямоугольников с неизотетными препятствиями.

Обобщения

Более высокие размерности

В трёхмерном пространстве известны алгоритмы поиска наибольших пустых изотетных кубоидов.

См. также

• Наибольшая пустая сфера
• Минимальный ограничивающий параллелепипед, Минимальный ограничивающий прямоугольник