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

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

Задачи такого вида возникают, например, задачах в автоматизации проектирования электроники, в разработке и проверке компоновки^[англ.] интегральных схем^[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].

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (18 июня 2018) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (18 июня 2018) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.