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

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

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

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

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

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

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

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

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

Область: прямоугольник, содержащий точки 
Задача, которую обсуждали Наамад, Ли и Шу в 1983, ставилась следующим образом: если дан прямоугольник A, содержащий n точек, нужно найти прямоугольник наибольшей площади, стороны которого параллельны прямоугольнику A, лежащий в прямоугольнике A и не содержащий какую-либо из данных точек. Наамад, Ли и Шу представили алгоритм с временной сложностью , где s — число допустимых решений, т.е. максимальных пустых прямоугольников. Они также доказали, что  и дали пример, в котором s квадратично зависит от n. Позднее появились статьи, представляющие более совершенные алгоритмы для задачи.

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

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

Обобщения

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

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

Примечания

Литература 

 . Описываются алгоритмы для операций с многоугольниками, применяемыми для автоматизации разработки электроники (проверка правил, схема цепей, размещение итрассировка)
 
 
 
 
 
 
 

Геометрические алгоритмы