www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. ↑ Naamad, Lee, Hsu, 1984, с. 267–277.
  2. Терещенко В. М. (2020). . Київ: Київський національний університет ім. Т. Шевченка. Факультет комп‘ютерних наук та кібернетики. с. 66. Архів оригіналу за 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 (6 листопада). — С. 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. — 6 листопада. — С. 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 (6 листопада). — С. 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. — 6 листопада. — С. 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 (6 листопада). — С. 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 (6 листопада). — С. 11–20. — DOI:10.1016/S0898-1221(98)00125-4.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Zada cha pro najbi lshij poro zhnij pryamoku tnik 2 ce zadacha poshuku pryamokutnika najbilshogo rozmiru yakij mozhna rozmistiti sered pereshkod na ploshini Isnuye kilka variantiv zadachi sho vidriznyayutsya osoblivostyami formulyuvannya zokrema vid sposobiv vimiryuvannya rozmiru tipiv pereshkod i oriyentaciyi pryamokutnika Najbilshi porozhni pryamokutniki zeleni z riznimi obmezhuvalnimi ob yektami z chornimi krayami Svitlo zelenij pryamokutnik ye pidoptimalnim ne maksimalnim rozv yazkom Prikladi A C mayut storoni paralelni osyam tobto storonam svitlo blakitnogo fonovogo pryamokutnika 1 Priklad E pokazuye variant zadachi z dovilnoyu oriyentaciyeyuZadachi takogo vidu vinikayut napriklad v avtomatizaciyi proyektuvannya elektroniki v rozrobci ta perevirci komponuvannya integralnih shem 3 Najbi lshij poro zhnij pryamoku tnik NPP ce pryamokutnik yakij ne mistitsya v inshomu porozhnomu pryamokutniku Kozhna storona NPP mezhuye z pereshkodoyu v inshomu vipadku storonu mozhna bulo b zsunuti zbilshuyuchi porozhnij pryamokutnik Takogo rodu zadachi vinikayut pri pererahuvanni najbilshih bilih pryamokutnikiv u segmentaciyi zobrazhen pid chas obrobki zobrazhen i rozpiznavannya obraziv 4 Zmist 1 Klasifikaciya 2 Okremi vipadki 2 1 Kvadrat najbilshoyi ploshi 2 2 Oblast pryamokutnik sho mistit tochki 2 3 Oblast pereshkodi u viglyadi vidrizkiv 3 Uzagalnennya 3 1 Vishi rozmirnosti 4 Div takozh 5 Primitki 6 LiteraturaKlasifikaciya red U terminah vimiryuvan najchastishe zustrichayutsya vipadki porozhnogo pryamokutnika najbilshoyi ploshi i porozhnogo pryamokutnika z najbilshim perimetrom 5 Insha vazhliva klasifikaciya chi nakladayetsya umova paralelnosti storin osyam chi storoni mozhut buti roztashovani dovilno Okremi vipadki red Kvadrat najbilshoyi ploshi red Vipadok koli shukanij pryamokutnik ye kvadratom zi storonami paralelnimi osyam mozhna rozglyanuti z vikoristannyam diagrami Voronogo z metrikoyu L 1 displaystyle L 1 nbsp dlya vidpovidnoyi mnozhini pereshkod analogichno zadachi pro najbilshu porozhnyu sferu Zokrema dlya vipadku tochok useredini pryamokutnika vidomij optimalnij algoritm z chasovoyu skladnistyu 8 n log n displaystyle Theta n log n nbsp 6 Oblast pryamokutnik sho mistit tochki red Zadacha yaku obgovoryuvali Naamad Li i Shu 1983 roku 1 stavilasya tak dlya danogo pryamokutnika A sho mistit n tochok potribno znajti pryamokutnik najbilshoyi ploshi storoni yakogo paralelni storonam pryamokutnika A yakij lezhit u pryamokutniku A i ne mistit zhodnoyi z danih tochok Naamad Li i Shu predstavili algoritm iz chasovoyu skladnistyu O min n 2 s log n displaystyle O min n 2 s log n nbsp de s chislo dopustimih rozv yazkiv tobto najbilshih porozhnih pryamokutnikiv Voni takozh doveli sho s O n 2 displaystyle s O n 2 nbsp i dali priklad u yakomu s kvadratichno zalezhit vid n Piznishe z yavilisya statti z opisom doskonalishih algoritmiv dlya ciyeyi zadachi Oblast pereshkodi u viglyadi vidrizkiv red Zadachu poshuku porozhnih izotetnih en 7 pryamokutnikiv sered izotetnih vidrizkiv pershimi rozglyanuli Nardi i Bhattachar ya 8 1990 roku 9 Piznishe rozglyanuto zagalnishu zadachu poshuku porozhnih izotetnih pryamokutnikiv iz neizotetnimi pereshkodami 8 Uzagalnennya red Vishi rozmirnosti red U trivimirnomu prostori vidomi algoritmi poshuku najbilshih porozhnih izotetnih kuboyidiv 10 Div takozh red Najbilsha porozhnya sfera Minimalna obmezhuvalna korobka Minimalnij obmezhuvalnij pryamokutnik Zadacha pro najmenshe koloPrimitki red a b Naamad Lee Hsu 1984 s 267 277 Tereshenko V M 2020 Analiz metodiv rozv yazannya optimizacijnih zadach obchislyuvalnoyi geometriyi Kiyiv Kiyivskij nacionalnij universitet im T Shevchenka Fakultet komp yuternih nauk ta kibernetiki s 66 Arhiv originalu za 2 kvitnya 2022 Procitovano 16 bereznya 2022 Ullman 1984 s Ch 9 Algorithms for VLSI Design Tools Baird Jones Fortune 1990 s 820 825 Aggearwal Suri 1987 s 278 290 Chazelle Drysdale III Lee 1984 s 43 54 Izotetnij bagatokutnik ce bagatokutnik storoni yakogo lezhat na dvoh puchkah pryamih a b Nardy Bhattacharya 1994 s 159 170 Nandy Bhattacharya Ray 1990 s 255 269 Nandy Bhattacharya 1998 s 11 20 Literatura red Jeffrey Ullman Ch 9 Algorithms for VLSI Design Tools Computational Aspects of VLSI Computer Science Press 1984 ISBN 0 914894 95 1 Opisano algoritmi dlya operacij nad mnogokutnikami sho zastosovuyutsya dlya avtomatizaciyi rozrobki elektroniki perevirka pravil shema lancyugiv rozmishennya i trasuvannya Baird H S Jones S E Fortune S J Image segmentation by shape directed covers Proc 10th International Conference on Pattern Recognition 1990 T 1 6 listopada S 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 6 listopada S 278 290 DOI 10 1145 41958 41988 Chazelle B Drysdale III R L Lee D T Computing the largest empty rectangle STACS 1984 1984 T 166 6 listopada S 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 6 listopada S 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 T 880 Lecture Notes in Computer Science Arhivovano z dzherela 16 bereznya 2022 Subhas C Nandy Bhargab B Bhattacharya Sibabrata Ray Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design Proc FST amp TCS 10 Lecture Notes in Computer Science 1990 T 437 6 listopada S 255 269 DOI 10 1007 3 540 53487 3 50 Nandy S C Bhattacharya B B Maximal Empty Cuboids among Points and Blocks Computers amp Mathematics with Applications 1998 T 36 vip 3 6 listopada S 11 20 DOI 10 1016 S0898 1221 98 00125 4 Otrimano z https uk wikipedia org w index php title Zadacha pro najbilshij porozhnij pryamokutnik amp oldid 36872534