Största tomma rektangeln

Maximalt tomma rektanglar (i grönt) med olika avgränsande objekt (med svart kontur) . Den ljusgröna rektangeln skulle vara en suboptimal (icke-maximal) lösning. AC är axelorienterade - parallella med axlar på det ljusblå "golvet" och även exempel på. E visar en maximal tom rektangel med godtycklig orientering

Inom beräkningsgeometri är det största problemet med tomma rektangel, maximala tomma rektangelproblem eller maximala tomma rektangelproblem , problemet med att hitta en rektangel av maximal storlek som ska placeras bland hinder i planet. Det finns ett antal varianter av problemet, beroende på särdragen hos denna generiska formulering, i synnerhet beroende på måttet på "storleken", domänen (typ av hinder) och rektangelns orientering.

Problemen av detta slag uppstår t.ex. inom elektronisk designautomation , vid design och verifiering av fysisk layout av integrerade kretsar .

En maximal tom rektangel är en rektangel som inte finns i en annan tom rektangel. Varje sida av en maximal tom rektangel ligger an mot ett hinder (annars kan sidan flyttas utåt, vilket ökar den tomma rektangeln). En tillämpning av detta slag är uppräkning av "maximala vita rektanglar" i bildsegmentering FoU för bildbehandling och mönsterigenkänning . I sammanhang med många algoritmer för de största tomma rektanglarna är "maximala tomma rektanglar" kandidatlösningar att överväga av algoritmen, eftersom det lätt kan bevisas att t.ex. en tom rektangel med maximal area är en maximal tom rektangel.

Klassificering

När det gäller storleksmått är de två vanligaste fallen den tomma rektangeln med största arean och den tomma rektangeln med största omkrets.

En annan viktig klassificering är om rektangeln söks bland axelorienterade eller godtyckligt orienterade rektanglar.

Speciella fall

Maximal area kvadrat

Fallet när den sökta rektangeln är en axelorienterad kvadrat kan behandlas med Voronoi-diagram i $L_{1}$ -mått för motsvarande hinderuppsättning, på samma sätt som det största problemet med tom cirkel . Speciellt när det gäller punkter inom rektangeln är en optimal algoritm för tidskomplexitet $\Theta (n\log n)$ känd.

Domän: rektangel som innehåller punkter

Ett problem som först diskuterades av Naamad, Lee och Hsu 1983 anges enligt följande: givet en rektangel A som innehåller n punkter, hitta en rektangel med största arean med sidor parallella med A som ligger inom A och inte innehåller någon av de givna poäng. Naamad, Lee och Hsu presenterade en algoritm för tidskomplexitet ${\displaystyle O(\min(n^{2},s\log n))} ,$ där s är antal möjliga lösningar, dvs maximalt tomma rektanglar. De bevisade också att $s=O(n^{2})$ och gav ett exempel där s är kvadratisk i n . Efteråt presenterade ett antal artiklar bättre algoritmer för problemet.

Domän: linjesegmenthinder

Problemet med tomma isotetiska rektanglar bland isotetiska linjesegment övervägdes först 1990. Senare övervägdes ett mer allmänt problem med tomma isotetiska rektanglar bland icke-isotetiska hinder.

Generaliseringar

Högre dimensioner

I 3-dimensionell rymd är algoritmer kända för att hitta ett största maximalt tomma isotetiska kuboidproblem , såväl som för uppräkning av alla maximala isotetiska tomma kuboider.

Se även