Největší prázdný obdélník - Largest empty rectangle

Maximální prázdné obdélníky (zeleně) s různými ohraničujícími objekty (s černým obrysem). Světle zelený obdélník by byl neoptimálním (ne maximálním) řešením. A-C jsou orientovány na osu - rovnoběžně s osami světle modré „podlahy“ a také příklady.[1] E ukazuje maximální prázdný obdélník s libovolnou orientací

v výpočetní geometrie, největší problém s prázdným obdélníkem,[2] problém maximálního prázdného obdélníku[3] nebo problém maximálního prázdného obdélníku,[4] je problém najít obdélník o maximální velikosti mezi překážky v rovině. Existuje řada variant problému v závislosti na zvláštnostech této obecné formulace, zejména v závislosti na míře „velikosti“, oblasti (typu překážek) a orientaci obdélníku.

Problémy tohoto druhu vznikají např. V automatizace elektronického designu, při návrhu a ověřování fyzické rozložení z integrované obvody.[5]

A maximální prázdný obdélník je obdélník, který není obsažen v jiném prázdném obdélníku. Každá strana maximálního prázdného obdélníku přiléhá k překážce (jinak může být strana posunuta směrem ven, čímž se zvětší prázdný obdélník). Aplikace tohoto druhu je výčet "maximálních bílých obdélníků" v segmentace obrazu Výzkum a vývoj zpracování obrazu a rozpoznávání vzorů.[6] V kontextech mnoha algoritmů pro největší prázdné obdélníky jsou „maximální prázdné obdélníky“ kandidátskými řešeními, která mají být algoritmem zohledněna, protože je snadno prokázáno, že např. prázdný obdélník o maximální ploše je maximální prázdný obdélník.

Klasifikace

Pokud jde o velikost, jsou to dva nejběžnější případy největší plocha prázdný obdélník a největší obvod prázdný obdélník.[7]

Další významnou klasifikací je, zda je hledán obdélník orientovaný na osu nebo libovolně orientované obdélníky.

Speciální případy

Čtverec s maximální plochou

Případ, kdy je hledaným obdélníkem osově orientovaný čtverec, lze léčit pomocí Voronoiovy diagramy v metriky pro odpovídající sadu překážek, podobně jako největší prázdný kruh problém. Zejména pro případ bodů v obdélníku optimální algoritmus časová složitost je známo.[8]

Doména: obdélník obsahující body

Problém poprvé diskutovali Naamad, Lee a Hsu v roce 1983[1] je uvedeno následovně: daný obdélník A obsahující n bodů, najděte největší obdélník se stranami rovnoběžnými s těmi A který leží uvnitř A a neobsahuje žádný z uvedených bodů. Naamad, Lee a Hsu představili algoritmus časová složitost , kde s je počet proveditelných řešení, tj. maximální prázdné obdélníky. Také to dokázali a uvedl příklad, ve kterém s je kvadratický v n. Poté řada článků představila lepší algoritmy pro řešení problému.

Doména: překážky úsečky

Problém prázdných izotetických obdélníků mezi izotetický nejprve byly uvažovány úsečky[9] v roce 1990.[10] Později byl uvažován obecnější problém prázdných izotetických obdélníků mezi neizotetickými překážkami.[9]

Zobecnění

Vyšší rozměry

V trojrozměrném prostoru jsou známé algoritmy pro hledání největšího maximálního prázdného izotetika kvádr problém, stejně jako pro výčet všech maximálních izotetických prázdných kvádrů.[11]

Viz také

Reference

  1. ^ A b A. Naamad, D. T. Lee a W.-L. Hsu (1984). "K problému maximálního prázdného obdélníku". Diskrétní aplikovaná matematika: 267–277. doi:10.1016 / 0166-218X (84) 90124-0.
  2. ^ „Hledat v Google Scholar pro„ použití výrazu s „největším prázdným obdélníkem“ “.
  3. ^ „Hledat v Google Scholar pro„ použití maximálního prázdného obdélníku “.
  4. ^ „Hledat v Google Scholar pro„ použití maximálního prázdného obdélníku “.
  5. ^ Jeffrey Ullman (1984). "Ch.9: Algoritmy pro návrhové nástroje VLSI". Výpočtové aspekty VLSI. Computer Science Press. ISBN  0-914894-95-1. popisuje algoritmy pro mnohoúhelníkové operace podílí se na automatizaci elektronického designu (kontrola návrhových pravidel, extrakce obvodu, umístění a směrování ).
  6. ^ Baird, H. S., Jones, S. E., Fortune, S.J. (1990). Msgstr "Segmentace obrazu podle tvarově orientovaných obalů". Proc. 10. mezinárodní konference dne Rozpoznávání vzorů. 1: 820–825. doi:10.1109 / ICPR.1990.118223.CS1 maint: více jmen: seznam autorů (odkaz)
  7. ^ Alok Aggearwal, Subhash Suri (1987). Msgstr "Rychlé algoritmy pro výpočet největšího prázdného obdélníku". Proc. 3. roč. Sympózium o výpočetní geometrii: 278–290. doi:10.1145/41958.41988.
  8. ^ B. Chazelle, R. L. Drysdale III a D. T. Lee (1984). Msgstr "Výpočet největšího prázdného obdélníku". STACS -1984, Přednášky z informatiky. 166: 43–54. doi:10.1007/3-540-12920-0_4.
  9. ^ A b "Umístění největšího prázdného obdélníku mezi libovolnými překážkami". Základy softwarové technologie a teoretické informatiky. str. 159.
  10. ^ Subhas C Nandy; Bhargab B Bhattacharya; Sibabrata Ray (1990). "Efektivní algoritmy pro identifikaci všech maximálních izotetických prázdných obdélníků v návrhu rozložení VLSI". Proc. FST & TCS - 10, Přednášky v informatice. 437: 255–269. doi:10.1007/3-540-53487-3_50.
  11. ^ SC Nandy; B.B. Bhattacharya (1998). "Maximální prázdné kvádry mezi body a bloky". Počítače a matematika s aplikacemi. 36 (3): 11–20. doi:10.1016 / S0898-1221 (98) 00125-4.