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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

См. также

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