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

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

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

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

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

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

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

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

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

Случай, когда искомый прямоугольник представляет собой квадрат, ориентированный по оси, можно рассматривать с помощью диаграмм Вороного в $L_{1}$ метрики для соответствующего набора препятствий, аналогично задаче о наибольшем пустом круге . В частности, для случая точек внутри прямоугольника оптимальный алгоритм временной сложности $\Theta (n\log n)$ известно. ^[8]

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

Проблема, впервые обсуждавшаяся Наамадом, Ли и Сюем в 1983 году. ^[1] формулируется следующим образом: для прямоугольника A, содержащего n точек, найти прямоугольник наибольшей площади со сторонами, параллельными сторонам A , который лежит внутри A и не содержит ни одной из данных точек. Наамад, Ли и Сюй представили алгоритм временной сложности. $O(\min(n^{2},s\log n))$ , где s — количество возможных решений, т.е. максимальных пустых прямоугольников. Они также доказали, что $s=O(n^{2})$ и привел пример, в котором s квадратично по n . Впоследствии в ряде статей были представлены лучшие алгоритмы решения этой проблемы.

Область: препятствия на сегменте линии.

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

Обобщения

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

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

См. также

Ссылки

^ Jump up to: ^а ^б А. Наамад, Д.Т. Ли и В.-Л. Сюй (1984). «О задаче о максимальном пустом прямоугольнике» . Дискретная прикладная математика . 8 (3): 267–277. дои : 10.1016/0166-218X(84)90124-0 .
^ «Поищите в Google Scholar термин «самый большой пустой прямоугольник» .
^ «Поищите в Google Scholar термин «максимальный пустой прямоугольник» .
^ «Поищите в Google Scholar термин «максимально пустой прямоугольник» .
^ Джеффри Уллман (1984). «Глава 9: Алгоритмы для инструментов проектирования СБИС». Вычислительные аспекты СБИС . Пресса по информатике. ISBN 0-914894-95-1 . описывает алгоритмы операций с полигонами , задействованных в автоматизации проектирования электроники ( проверка правил проектирования , извлечение схем , размещение и маршрутизация ).
^ Бэрд, Х.С., Джонс, С.Э., Форчун, С.Дж. (1990). «Сегментация изображений по обложкам, ориентированным на форму». [1990] Труды. 10-я Международная конференция по распознаванию образов . Том. 1. С. 820–825. дои : 10.1109/ICPR.1990.118223 . ISBN 0-8186-2062-5 . S2CID 62735730 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Алок Аггеарвал , Субхаш Сури (1987). «Быстрые алгоритмы вычисления наибольшего пустого прямоугольника». Материалы третьего ежегодного симпозиума по вычислительной геометрии - SCG '87 . стр. 278–290. дои : 10.1145/41958.41988 . ISBN 0897912314 . S2CID 18500442 .
^ Б. Шазель , Р.Л. Дрисдейл III и Д.Т. Ли (1984). «Вычисление самого большого пустого прямоугольника». STACS-1984, Конспекты лекций по информатике . Конспекты лекций по информатике. 166 : 43–54. дои : 10.1007/3-540-12920-0_4 . ISBN 978-3-540-12920-2 .
^ Jump up to: ^а ^б Тиагараджан, П.С. (23 ноября 1994 г.). «Расположение наибольшего пустого прямоугольника среди произвольных препятствий» . Основы программных технологий и теоретической информатики . Спрингер. п. 159. ИСБН 9783540587156 .
^ Субхас С. Нэнди; Бхаргаб Б. Бхаттачарья; Сибабрата Рэй (1990). «Эффективные алгоритмы идентификации всех максимальных изотетических пустых прямоугольников в макете СБИС». Учеб. FST и TCS – 10, Конспекты лекций по информатике . Конспекты лекций по информатике. 437 : 255–269. дои : 10.1007/3-540-53487-3_50 . ISBN 978-3-540-53487-7 .
^ СК Нанди; Б.Б. Бхаттачарья (1998). «Максимальные пустые кубоиды среди точек и блоков» . Компьютеры и математика с приложениями . 36 (3): 11–20. дои : 10.1016/S0898-1221(98)00125-4 .

[hsu1981-1] Jump up to: ^а ^б А. Наамад, Д.Т. Ли и В.-Л. Сюй (1984). «О задаче о максимальном пустом прямоугольнике» . Дискретная прикладная математика . 8 (3): 267–277. дои : 10.1016/0166-218X(84)90124-0 .

[2] «Поищите в Google Scholar термин «самый большой пустой прямоугольник» .

[3] «Поищите в Google Scholar термин «максимальный пустой прямоугольник» .

[4] «Поищите в Google Scholar термин «максимально пустой прямоугольник» .

[5] Джеффри Уллман (1984). «Глава 9: Алгоритмы для инструментов проектирования СБИС». Вычислительные аспекты СБИС . Пресса по информатике. ISBN 0-914894-95-1 . описывает алгоритмы операций с полигонами , задействованных в автоматизации проектирования электроники ( проверка правил проектирования , извлечение схем , размещение и маршрутизация ).

[6] Бэрд, Х.С., Джонс, С.Э., Форчун, С.Дж. (1990). «Сегментация изображений по обложкам, ориентированным на форму». [1990] Труды. 10-я Международная конференция по распознаванию образов . Том. 1. С. 820–825. дои : 10.1109/ICPR.1990.118223 . ISBN 0-8186-2062-5 . S2CID 62735730 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[7] Алок Аггеарвал , Субхаш Сури (1987). «Быстрые алгоритмы вычисления наибольшего пустого прямоугольника». Материалы третьего ежегодного симпозиума по вычислительной геометрии - SCG '87 . стр. 278–290. дои : 10.1145/41958.41988 . ISBN 0897912314 . S2CID 18500442 .

[8] Б. Шазель , Р.Л. Дрисдейл III и Д.Т. Ли (1984). «Вычисление самого большого пустого прямоугольника». STACS-1984, Конспекты лекций по информатике . Конспекты лекций по информатике. 166 : 43–54. дои : 10.1007/3-540-12920-0_4 . ISBN 978-3-540-12920-2 .

[noniso-9] Jump up to: ^а ^б Тиагараджан, П.С. (23 ноября 1994 г.). «Расположение наибольшего пустого прямоугольника среди произвольных препятствий» . Основы программных технологий и теоретической информатики . Спрингер. п. 159. ИСБН 9783540587156 .

[10] Субхас С. Нэнди; Бхаргаб Б. Бхаттачарья; Сибабрата Рэй (1990). «Эффективные алгоритмы идентификации всех максимальных изотетических пустых прямоугольников в макете СБИС». Учеб. FST и TCS – 10, Конспекты лекций по информатике . Конспекты лекций по информатике. 437 : 255–269. дои : 10.1007/3-540-53487-3_50 . ISBN 978-3-540-53487-7 .

[11] СК Нанди; Б.Б. Бхаттачарья (1998). «Максимальные пустые кубоиды среди точек и блоков» . Компьютеры и математика с приложениями . 36 (3): 11–20. дои : 10.1016/S0898-1221(98)00125-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]