Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  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. — .. Описано алгоритми для операцій над многокутниками, що застосовуються для автоматизації розробки електроніки (перевірка правил, схема ланцюгів, розміщення і трасування)
  • Baird, H. S., Jones, S. E., Fortune, S.J. Image segmentation by shape-directed covers // Proc. 10th International Conference on Pattern Recognition. — 1990. — Т. 1 (8 липня). — С. 820–825. — DOI:10.1109/ICPR.1990.118223.
  • Alok Aggearwal, Subhash Suri. Fast algorithms for computing the largest empty rectangle // Proc. 3rd Annu. . — 1987. — 8 липня. — С. 278–290. — DOI:10.1145/41958.41988.
  • Chazelle B., Drysdale III R. L., Lee D. T. Computing the largest empty rectangle // -1984. — 1984. — Т. 166 (8 липня). — С. 43–54. — (). — 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. — 8 липня. — С. 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 (8 липня). — С. 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 (8 липня). — С. 11–20. — DOI:10.1016/S0898-1221(98)00125-4.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zada cha pro najbi lshij poro zhnij pryamoku tnik 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 Priklad E pokazuye variant zadachi z dovilnoyu oriyentaciyeyu Zadachi takogo vidu vinikayut napriklad v avtomatizaciyi proyektuvannya elektroniki v rozrobci ta perevirci komponuvannya integralnih shem 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 KlasifikaciyaU terminah vimiryuvan najchastishe zustrichayutsya vipadki porozhnogo pryamokutnika najbilshoyi ploshi i porozhnogo pryamokutnika z najbilshim perimetrom Insha vazhliva klasifikaciya chi nakladayetsya umova paralelnosti storin osyam chi storoni mozhut buti roztashovani dovilno Okremi vipadkiKvadrat najbilshoyi ploshi Vipadok koli shukanij pryamokutnik ye kvadratom zi storonami paralelnimi osyam mozhna rozglyanuti z vikoristannyam diagrami Voronogo z metrikoyu L1 displaystyle L 1 dlya vidpovidnoyi mnozhini pereshkod analogichno zadachi pro najbilshu porozhnyu sferu Zokrema dlya vipadku tochok useredini pryamokutnika vidomij optimalnij algoritm z chasovoyu skladnistyu 8 nlog n displaystyle Theta n log n Oblast pryamokutnik sho mistit tochki Zadacha yaku obgovoryuvali Naamad Li i Shu 1983 roku 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 n2 slog n displaystyle O min n 2 s log n de s chislo dopustimih rozv yazkiv tobto najbilshih porozhnih pryamokutnikiv Voni takozh doveli sho s O n2 displaystyle s O n 2 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 Zadachu poshuku porozhnih en pryamokutnikiv sered izotetnih vidrizkiv pershimi rozglyanuli Nardi i Bhattachar ya 1990 roku Piznishe rozglyanuto zagalnishu zadachu poshuku porozhnih izotetnih pryamokutnikiv iz neizotetnimi pereshkodami UzagalnennyaVishi rozmirnosti U trivimirnomu prostori vidomi algoritmi poshuku najbilshih porozhnih izotetnih kuboyidiv Div takozhNajbilsha porozhnya sfera Minimalna obmezhuvalna korobka Minimalnij obmezhuvalnij pryamokutnik Zadacha pro najmenshe koloPrimitkiNaamad Lee Hsu 1984 s 267 277 Tereshenko V M 2020 PDF Kiyiv Kiyivskij nacionalnij universitet im T Shevchenka Fakultet komp yuternih nauk ta kibernetiki s 66 Arhiv originalu PDF 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 Nardy Bhattacharya 1994 s 159 170 Nandy Bhattacharya Ray 1990 s 255 269 Nandy Bhattacharya 1998 s 11 20 LiteraturaJeffrey 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 8 lipnya S 820 825 DOI 10 1109 ICPR 1990 118223 Alok Aggearwal Subhash Suri Fast algorithms for computing the largest empty rectangle Proc 3rd Annu 1987 8 lipnya S 278 290 DOI 10 1145 41958 41988 Chazelle B Drysdale III R L Lee D T Computing the largest empty rectangle 1984 1984 T 166 8 lipnya S 43 54 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 8 lipnya 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 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 8 lipnya 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 8 lipnya S 11 20 DOI 10 1016 S0898 1221 98 00125 4

Дата публікації:
Топ