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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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