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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Шаблон:Книга. Описано алгоритми для операцій над многокутниками, що застосовуються для автоматизації розробки електроніки (перевірка правил, схема ланцюгів, розміщення і трасування)
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття