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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

См. также

Примечания
  1. Naamad, Lee, Hsu, 1984, с. 267–277.
  2. Search Google Scholar for "largest empty rectangle" term usage.
  3. Search Google Scholar for "maximum empty rectangle" term usage.
  4. Search Google Scholar for "maximal empty rectangle" term usage.
  5. Ullman, 1984, с. Ch.9: Algorithms for VLSI Design Tools.
  6. Baird, Jones, Fortune, 1990, с. 820–825.
  7. Aggearwal, Suri, 1987, с. 278–290.
  8. Chazelle, Drysdale III, Lee, 1984, с. 43–54.
  9. Изотетный многоугольник — это многоугольник, стороны которого лежат на двух пучках прямых.
  10. Nardy, Bhattacharya, 1994, с. 159-170.
  11. Nandy, Bhattacharya, Ray, 1990, с. 255–269.
  12. Nandy, Bhattacharya, 1998, с. 11–20.

Литература
  • Jeffrey Ullman. Ch.9: Algorithms for VLSI Design Tools // Computational Aspects of VLSI. — Computer Science Press, 1984. — ISBN 0-914894-95-1.. Описываются алгоритмы для операций с многоугольниками, применяемыми для автоматизации разработки электроники (проверка правил, схема цепей, размещение итрассировка)
  • Baird, H. S., Jones, S. E., Fortune, S.J. Image segmentation by shape-directed covers // Proc. 10th International Conference on Pattern Recognition. — 1990. — Т. 1. — С. 820–825. — doi:10.1109/ICPR.1990.118223.
  • Alok Aggearwal, Subhash Suri. Fast algorithms for computing the largest empty rectangle // Proc. 3rd Annu. Symposium on Computational Geometry. — 1987. — С. 278–290. — doi:10.1145/41958.41988.
  • Chazelle B., Drysdale III R. L., Lee D. T. Computing the largest empty rectangle // STACS-1984. — 1984. — Т. 166. — С. 43–54. — doi:10.1007/3-540-12920-0_4.
  • Naamad A., Lee D. T., Hsu W.-L. On the Maximum Empty Rectangle Problem // Discrete Applied Mathematics. — 1984. — С. 267–277. — doi:10.1016/0166-218X(84)90124-0.
  • Subhas C. Nardy, Bhargab B. Bhattacharya. Location of Largest Empty Rectangle among Arbitrary Obstacles // Foundations of Software Technology and Theoretical Computer Science / Thiagarajan P.S.. — 1994. — Т. 880. — (Lecture Notes in Computer Science).
  • Subhas C Nandy, Bhargab B Bhattacharya, Sibabrata Ray. Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design // Proc. FST & TCS – 10, Lecture Notes in Computer Science. — 1990. — Т. 437. — С. 255–269. — doi:10.1007/3-540-53487-3_50.
  • Nandy S.C., Bhattacharya B.B. Maximal Empty Cuboids among Points and Blocks // Computers & Mathematics with Applications. — 1998. — Т. 36, вып. 3. — С. 11–20. — doi:10.1016/S0898-1221(98)00125-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.