Вікіпедія

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

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

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

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

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

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

Класифікація ред.

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

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

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

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

Випадок, коли шуканий прямокутник є квадратом зі сторонами, паралельними осям, можна розглянути з використанням діаграми Вороного з метрикою   для відповідної множини перешкод, аналогічно задачі про найбільшу порожню сферу. Зокрема, для випадку точок усередині прямокутника відомий оптимальний алгоритм з часовою складністю  [6].

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

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

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

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

Узагальнення ред.

Вищі розмірності ред.

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

Див. також ред.

Примітки ред.

  1. ↑ а б Naamad, Lee, Hsu, 1984, с. 267–277.
  2. ↑ Терещенко В. М. (2020). Аналіз методів розв’язання оптимізаційних задач обчислювальної геометрії (PDF). Київ: Київський національний університет ім. Т. Шевченка. Факультет комп‘ютерних наук та кібернетики. с. 66. Архів оригіналу (PDF) за 2 квітня 2022. Процитовано 16 березня 2022.
  3. ↑ Ullman, 1984, с. Ch.9: Algorithms for VLSI Design Tools.
  4. ↑ Baird, Jones, Fortune, 1990, с. 820–825.
  5. ↑ Aggearwal, Suri, 1987, с. 278–290.
  6. ↑ Chazelle, Drysdale III, Lee, 1984, с. 43–54.
  7. ↑ Ізотетний багатокутник — це багатокутник, сторони якого лежать на двох пучках прямих.
  8. ↑ а б Nardy, Bhattacharya, 1994, с. 159-170.
  9. ↑ Nandy, Bhattacharya, Ray, 1990, с. 255–269.
  10. ↑ 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 (21 квітня). — С. 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. — 21 квітня. — С. 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 (21 квітня). — С. 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. — 21 квітня. — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 11–20. — DOI:10.1016/S0898-1221(98)00125-4.
Отримано з https://uk.wikipedia.org/w/index.php?title=Задача_про_найбільший_порожній_прямокутник&oldid=36872534