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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

См. также

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

Литература

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