Задача про найбільший порожній прямокутник

Найбільші порожні прямокутники (зелені) з різними обмежувальними об'єктами (з чорними краями). Світло-зелений прямокутник є підоптимальним (не максимальним) розв'язком. Приклади A-C мають сторони, паралельні осям, тобто сторонам світло-блакитного фонового прямокутника. Приклад E показує варіант задачі з довільною орієнтацією

Зада́ча про найбі́льший поро́жній прямоку́тник — це задача пошуку прямокутника найбільшого розміру, який можна розмістити серед перешкод на площині. Існує кілька варіантів задачі, що відрізняються особливостями формулювання, зокрема, від способів вимірювання «розміру», типів перешкод і орієнтації прямокутника.

Задачі такого виду виникають, наприклад, в автоматизації проєктування електроніки, в розробці та перевірці компонування інтегральних схем.

Найбі́льший поро́жній прямоку́тник (НПП) — це прямокутник, який не міститься в іншому порожньому прямокутнику. Кожна сторона НПП межує з перешкодою (в іншому випадку сторону можна було б зсунути, збільшуючи порожній прямокутник). Такого роду задачі виникають при перерахуванні «найбільших білих прямокутників» у сегментації зображень під час обробки зображень і розпізнавання образів.

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

У термінах вимірювань найчастіше зустрічаються випадки порожнього прямокутника найбільшої площі і порожнього прямокутника з найбільшим периметром.

Інша важлива класифікація — чи накладається умова паралельності сторін осям, чи сторони можуть бути розташовані довільно.

Окремі випадки

Квадрат найбільшої площі

Випадок, коли шуканий прямокутник є квадратом зі сторонами, паралельними осям, можна розглянути з використанням діаграми Вороного з метрикою $L_{1}$ для відповідної множини перешкод, аналогічно задачі про найбільшу порожню сферу. Зокрема, для випадку точок усередині прямокутника відомий оптимальний алгоритм з часовою складністю $\Theta (n\log n)$.

Область: прямокутник, що містить точки

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

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

Задачу пошуку порожніх ізотетних прямокутників серед ізотетних відрізків першими розглянули Нарді і Бхаттачар'я 1990 року. Пізніше розглянуто загальнішу задачу пошуку порожніх ізотетних прямокутників із неізотетними перешкодами.

Узагальнення

Вищі розмірності

У тривимірному просторі відомі алгоритми пошуку найбільших порожніх ізотетних кубоїдів.

Див. також

• Найбільша порожня сфера
• Мінімальна обмежувальна коробка
• Мінімальний обмежувальний прямокутник
• Задача про найменше коло

Література

• 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 (10 листопада). — С. 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. — 10 листопада. — С. 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 (10 листопада). — С. 43–54. — (Lecture Notes in Computer Science). — 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. — 10 листопада. — С. 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) Архівовано з джерела 16 березня 2022
• 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 (10 листопада). — С. 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 (10 листопада). — С. 11–20. — DOI:10.1016/S0898-1221(98)00125-4.