Самый большой пустой прямоугольник - Largest empty rectangle

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

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

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

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

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

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

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

Особые случаи

Площадь максимальной площади

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

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

Проблема, впервые обсужденная Наамадом, Ли и Хсу в 1983 году.[1] формулируется следующим образом: учитывая прямоугольник А содержащий п точек, найдите прямоугольник наибольшей площади со сторонами, параллельными сторонам А который находится внутри А и не содержит ни одной из указанных точек. Наамад, Ли и Сюй представили алгоритм временная сложность , где s - количество возможных решений, т. е. максимальных пустых прямоугольников. Они также доказали, что и привел пример, в котором s квадратично по п. Впоследствии в ряде статей были представлены лучшие алгоритмы решения проблемы.

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

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

Обобщения

Высшие измерения

В трехмерном пространстве известны алгоритмы нахождения наибольшего максимального пустого изотетического кубовид задачи, а также для перечисления всех максимальных изотетических пустых кубоидов.[11]

Смотрите также

использованная литература

  1. ^ а б А. Наамад, Д. Т. Ли и W.-L. Сюй (1984). «К задаче о максимальном пустом прямоугольнике». Дискретная прикладная математика: 267–277. Дои:10.1016 / 0166-218X (84) 90124-0.
  2. ^ "Найдите в Google Scholar" термин "самый большой пустой прямоугольник".
  3. ^ "Найдите в Google Scholar" термин "максимальный пустой прямоугольник".
  4. ^ "Найдите в Google Scholar" термин "максимальный пустой прямоугольник".
  5. ^ Джеффри Уллман (1984). «Глава 9: Алгоритмы для средств проектирования СБИС». Вычислительные аспекты СБИС. Computer Science Press. ISBN  0-914894-95-1. описывает алгоритмы для полигональные операции занимается автоматизацией электронного проектирования (проверка правил проектирования, контур извлечения, размещение и маршрутизация ).
  6. ^ Бэрд, Х.С., Джонс, С.Е., Fortune, S.J. (1990). «Сегментация изображения по фигурным обложкам». Proc. 10-я Международная конференция по Распознавание образов. 1: 820–825. Дои:10.1109 / ICPR.1990.118223.CS1 maint: несколько имен: список авторов (ссылка на сайт)
  7. ^ Алок Аггеервал, Субхаш Сури (1987). «Быстрые алгоритмы вычисления самого большого пустого прямоугольника». Proc. 3-й год. Симпозиум по вычислительной геометрии: 278–290. Дои:10.1145/41958.41988.
  8. ^ Б. Шазель, Р. Л. Дрисдейл III и Д. Т. Ли (1984). «Вычисление самого большого пустого прямоугольника». STACS -1984, Конспект лекций по информатике. 166: 43–54. Дои:10.1007/3-540-12920-0_4.
  9. ^ а б «Расположение наибольшего пустого прямоугольника среди произвольных препятствий». Основы программных технологий и теоретической информатики. п. 159.
  10. ^ Subhas C Nandy; Бхаргаб Б Бхаттачарья; Сибабрата Рэй (1990). «Эффективные алгоритмы для определения всех максимально изотетических пустых прямоугольников в макете СБИС». Proc. FST & TCS - 10, Конспект лекций по информатике. 437: 255–269. Дои:10.1007/3-540-53487-3_50.
  11. ^ С.К. Нанди; Б. Б. Бхаттачарья (1998). «Максимальные пустые кубоиды среди точек и блоков». Компьютеры и математика с приложениями. 36 (3): 11–20. Дои:10.1016 / S0898-1221 (98) 00125-4.