Maximalt disjunkt set

Inom beräkningsgeometri är en maximal disjoint set ( MDS ) en största uppsättning icke-överlappande geometriska former valda från en given uppsättning kandidatformer.

Varje uppsättning icke-överlappande former är en oberoende uppsättning i formernas skärningsdiagram . Därför är MDS-problemet ett specialfall av maximal independent set) . MIS- problemet ( Båda problemen är NP kompletta , men att hitta en MDS kan vara lättare än att hitta en MIS i två avseenden:

För det allmänna MIS-problemet är de mest kända exakta algoritmerna exponentiella. I vissa geometriska skärningsdiagram finns det subexponentiella algoritmer för att hitta en MDS.
Det allmänna MIS-problemet är svårt att uppskatta och har inte ens en approximation med konstant faktor. I vissa geometriska skärningsdiagram finns det polynom-tidsapproximationsscheman (PTAS) för att hitta en MDS.

Att hitta en MDS är viktigt i applikationer som automatisk etikettplacering , VLSI- kretsdesign och cellulär frekvensdelningsmultiplexering .

MDS-problemet kan generaliseras genom att tilldela en annan vikt till varje form och söka efter en disjunkt uppsättning med en maximal totalvikt.

I följande text betecknar MDS( C ) den maximala disjunktuppsättningen i en uppsättning C .

giriga algoritmer

Givet en uppsättning C av former, kan en approximation till MDS( C ) hittas med följande giriga algoritm :

INITIALISERING: Initiera en tom uppsättning, S .
SÖK: För varje form x i C :
1. Beräkna N(x) - delmängden av alla former i C som skär x (inklusive x själv).
2. Beräkna den största oberoende mängden i denna delmängd: MDS(N(x)) .
3. Välj ett x så att |MDS(N(x))| är minimerad.
Lägg till x till S .
Ta bort x och N(x) från C .
Om det finns former i C , gå tillbaka till Sök.
END: returnera setet S .

För varje form x som vi lägger till S , förlorar vi formerna i N(x) , eftersom de skärs av x och därför inte kan läggas till S senare. Vissa av dessa former korsar dock själva varandra, och därför är det i alla fall inte möjligt att de alla är i den optimala lösningen MDS(S) . Den största delmängden av former som kan vara i den optimala lösningen är MDS(N(x)) . Välj därför ett x som minimerar |MDS(N(x))| minimerar förlusten från att lägga till x till S .

I synnerhet om vi kan garantera att det finns ett x för vilket |MDS(N(x))| begränsas av en konstant (säg, M ), så ger denna giriga algoritm en konstant M -faktor approximation, eftersom vi kan garantera att:

$|S|\geq {\frac {|MDS(C)|}{M}}$

En sådan övre gräns M finns för flera intressanta fall:

1-dimensionella intervall: exakt polynomalgoritm

När C är en uppsättning intervall på en linje, M =1, och därmed hittar den giriga algoritmen den exakta MDS. För att se detta, anta wlog att intervallen är vertikala och låt x vara intervallet med den högsta bottenslutpunkten . Alla andra intervall som skärs av x måste passera dess nedre ändpunkt. Därför skär alla intervall i N(x) varandra, och MDS(N(x)) har en storlek på högst 1 (se figur).

Därför, i det 1-dimensionella fallet, kan MDS hittas exakt i tiden O ( n log n ):

Sortera intervallen i stigande ordning efter deras nedre slutpunkter (detta tar tid O ( n log n )).
Lägg till ett intervall med den högsta bottenslutpunkten och ta bort alla intervall som skär det.
Fortsätt tills inga intervaller återstår.

Denna algoritm är analog med den tidigaste deadline första schemaläggningslösningen för intervallschemaläggningsproblemet .

I motsats till det 1-dimensionella fallet blir MDS-problemet i 2 eller fler dimensioner NP-komplett, och har således antingen exakta superpolynomalgoritmer eller approximativa polynomalgoritmer.

Fettformer: approximationer med konstant faktor

När C är en uppsättning enhetsskivor, M =3, eftersom skivan längst till vänster (skivan vars mitt har den minsta x- koordinaten) skär högst 3 andra disjunkta skivor (se figur). Därför ger den giriga algoritmen en 3-approximation, dvs den hittar en disjunkt uppsättning med en storlek på minst MDS(C) /3.

På liknande sätt, när C är en uppsättning axelparallella enhetskvadrater, M =2.

När C är en uppsättning skivor av godtycklig storlek, M =5, eftersom skivan med den minsta radien skär högst 5 andra disjunkta skivor (se figur).

På liknande sätt, när C är en uppsättning av axelparallella kvadrater med godtycklig storlek, är M =4.

Andra konstanter kan beräknas för andra reguljära polygoner .

Dela-och-härska algoritmer

Det vanligaste tillvägagångssättet för att hitta en MDS är dela-och-härska. En typisk algoritm i detta tillvägagångssätt ser ut som följande:

Dela upp den givna uppsättningen former i två eller flera delmängder, så att formerna i varje delmängd inte kan överlappa formerna i andra delmängder på grund av geometriska överväganden.
Rekursivt hitta MDS i varje delmängd separat.
Returnera föreningen av MDS från alla delmängder.

Den största utmaningen med detta tillvägagångssätt är att hitta ett geometriskt sätt att dela upp mängden i delmängder. Detta kan kräva att ett litet antal former som inte passar in i någon av delmängderna kasseras, vilket förklaras i följande underavsnitt.

Axelparallella rektanglar med samma höjd: 2-approximation

Låt C vara en uppsättning av n axelparallella rektanglar i planet, alla med samma höjd H men med olika längder. Följande algoritm hittar en disjunkt uppsättning med en storlek på minst |MDS( C )|/2 i tiden O ( n log n ):

Rita m horisontella linjer, så att:
1. Avståndet mellan två linjer är strikt mer än H .
2. Varje linje skär minst en rektangel (därav m ≤ n ).
3. Varje rektangel skärs av exakt en linje.
Eftersom höjden på alla rektanglar är H , är det inte möjligt att en rektangel skärs av mer än en linje. Därför delar linjerna upp uppsättningen av rektanglar i m delmängder ( $R_{i},\ldots ,R_{m}$ ) – varje delmängd inkluderar rektanglarna som skärs av en enda linje.
För varje delmängd $R_{i}$ , beräkna en exakt MDS $M_{i}$ med hjälp av den endimensionella giriga algoritmen (se ovan).
Genom konstruktion kan rektanglarna i ( $R_{i}$ $R_{i}$ ) skära endast rektanglar i $R_{i+1}$ $R_{{i+1}}$ eller i $R_{i- 1}$ $R_{{i-1}}$ . Därför är var och en av följande två fackföreningar en osammanhängande uppsättning:
- Union av udda MDS: $M_{1}\cup M_{3}\cup \cdots$
- Union av jämna MDS: $M_{2}\cup M_{4}\cup \cdots$
Returnera den största av dessa två fackföreningar. Dess storlek måste vara minst |MDS|/2.

Axelparallella rektanglar med samma höjd: PTAS

Låt C vara en uppsättning av n axelparallella rektanglar i planet, alla med samma höjd men med olika längder. Det finns en algoritm som hittar en disjunkt uppsättning med en storlek på minst |MDS( C )|/(1 + 1/ k ) i tiden O ( n ^{2 k −1} ), för varje konstant k > 1.

Algoritmen är en förbättring av den ovan nämnda 2-approximationen, genom att kombinera dynamisk programmering med växlingstekniken från Hochbaum och Maass.

Denna algoritm kan generaliseras till d dimensioner. Om etiketterna har samma storlek i alla dimensioner utom en, är det möjligt att hitta en liknande approximation genom att tillämpa dynamisk programmering längs en av dimensionerna. Detta minskar också tiden till n^O(1/e).

Axelparallella rektanglar: Logaritmisk faktorapproximation

Låt C vara en uppsättning av n axelparallella rektanglar i planet. Följande algoritm hittar en disjunkt uppsättning med en storlek på minst ${\frac {|MDS(C)|}{\log {n}}}$ i tid $O(n\log {n})$ :

INITIALISERING: sortera de horisontella kanterna på de givna rektanglarna efter deras y -koordinater och de vertikala kanterna efter deras x -koordinater (detta steg tar tid O ( n log n )).
STOPPVILLKOR: Om det finns högst n ≤ 2 former, beräkna MDS direkt och returnera.
REKURSIV DEL:
1. Låt $x_{\mathrm {med} }$ vara median x -koordinaten.
2. Dela in inmatningsrektanglarna i tre grupper enligt deras relation till linjen $x=x_{\mathrm {med} }$ : de som är helt till vänster ( $R_ {\mathrm {vänster} }$ ), de som är helt till höger ( $R_{\mathrm {right} }$ ), och de som skärs av den ( $R_ {\mathrm {int} }$ ). Genom konstruktion är kardinaliteterna för $R_{\mathrm {left} }$ och $R_{\mathrm {right} }$ högst n /2.
3. Beräkna rekursivt en ungefärlig MDS i $R_{\mathrm {left} }$ ( ${\displaystyle M_{\mathrm {left} }} )$ och i $R_{\mathrm {höger} }$ ( $M_{\mathrm {höger} }$ ), och beräkna deras förening. Genom konstruktion är rektanglarna i $M_{\mathrm {left} }$ och $M_{\mathrm {right} }$ alla disjunkta, så $M_{\mathrm {vänster} }\cup M_{\mathrm {höger} }$ är en disjunkt uppsättning.
4. Beräkna en exakt MDS i $R_{\mathrm {int} }$ ( ${\displaystyle M_{\mathrm {int} }})$ . Eftersom alla rektanglar i $R_{\mathrm {int} }$ skär en enda vertikal linje ${\displaystyle x=x_{\mathrm {med} }} ,$ är denna beräkning ekvivalent att hitta en MDS från en uppsättning intervall, och kan lösas exakt i tiden O(n log n) (se ovan).
Returnera antingen $M_{\mathrm {vänster} }\cup M_{\mathrm {höger} }$ eller $M_{\mathrm {int } }$ – vilken av dem som är störst.

Det kan bevisas genom induktion att, i det sista steget, antingen $M_{\mathrm {vänster} }\cup M_{\mathrm {höger} }$ eller $M_{\mathrm {int} }$ har en kardinalitet på minst ${\frac {|MDS(C)|}{\log {n}}}$ .

Chalermsookk och Chuzoy har förbättrat faktorn till $O(\log {\log {n}})$ .

Chalermsook och Walczak har presenterat en $O(\log {\log {n}})$ -approximationsalgoritm till den mer allmänna inställningen, där varje rektangel har en vikt och målet är att hitta en oberoende uppsättning av maximal totalvikt.

Axelparallella rektanglar: approximation med konstant faktor

Under lång tid var det inte känt om en konstantfaktorapproximation existerar för axelparallella rektanglar med olika längder och höjder. Det förmodades att en sådan approximation kunde hittas med hjälp av giljotinsnitt . Speciellt om det finns en giljotinseparation av axlar-parallella rektanglar där $\Omega (n)$ rektanglar är separerade, då kan den användas i en dynamisk programmeringsmetod för att hitta en approximation med konstant faktor till MDS.

Hittills är det inte känt om en sådan giljotinseparation existerar. Det finns dock approximationsalgoritmer med konstant faktor som använder icke-giljotinsnitt:

Joseph SB Mitchell presenterade en 10-faktors approximationsalgoritm. Hans algoritm är baserad på att dela upp planet i hörnklippta rektanglar .
Gálvez, Khan, Mari, Mömke, Pittu och Wiese presenterade en algoritm som delar upp planet i en mer allmän klass av polygoner. Detta förenklar analysen och förbättrar approximationen till 6-faktor. Dessutom förbättrade de approximationen till 3-faktor och sedan till (2+ε)-faktor.

Feta föremål med identiska storlekar: PTAS

Låt C vara en uppsättning av n kvadrater eller cirklar av samma storlek. Hochbaum och Maass presenterade ett polynom-tidsapproximationsschema för att hitta en MDS med hjälp av en enkel shifted-grid-strategi. Den hittar en lösning inom (1 − ε) av maximum i tid n ^{O (1/ ε ² )} tid och linjärt rum. Strategin generaliserar till alla samlingar av feta föremål av ungefär samma storlek (dvs när förhållandet mellan maximi och minsta storlek begränsas av en konstant).

Feta föremål med godtyckliga storlekar: PTAS

Låt C vara en uppsättning av n feta objekt , såsom kvadrater eller cirklar , av godtyckliga storlekar. Det finns en PTAS för att hitta en MDS baserad på multi-level grid alignment. Det har upptäckts av två grupper på ungefär samma tid och beskrivits på två olika sätt.

Nivåuppdelning

En algoritm av Erlebach, Jansen och Seidel hittar en disjunkt uppsättning med en storlek på minst (1 − 1/ k ) ² · |MDS( C )| i tiden n ^{O ( k ² )} , för varje konstant k > 1. Det fungerar på följande sätt.

Skala skivorna så att den minsta skivan har diameter 1. Dela upp skivorna i nivåer, baserat på logaritmen för deras storlek. Dvs den j -:e nivån innehåller alla skivor med diameter mellan ( k + 1) ^j och ( k + 1) ^{j +1} , för j ≤ 0 (den minsta skivan är i nivå 0).

För varje nivå j lägg på ett rutnät på planet som består av linjer som är ( k + 1) ^{j +1} från varandra. Genom sin konstruktion kan varje skiva skära högst en horisontell linje och en vertikal linje från dess nivå.

För varje r , s mellan 0 och k , definiera D ( r , s ) som delmängden av skivor som inte skärs av någon horisontell linje vars index modulo k är r , och inte heller av någon vertikal linje vars indexmodulu k är s . Enligt duvhålsprincipen finns det minst ett par (r,s) så att ${\displaystyle |\mathrm {MDS} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {MDS} |} ,$ dvs. , vi kan bara hitta MDS i D ( r , s ) och missa bara en liten del av diskarna i den optimala lösningen:

För alla k ² möjliga värden på r , s (0 ≤ r , s < k ), beräkna D ( r , s ) med dynamisk programmering .
Returnera den största av dessa k ² set.

Förskjutna quadtrees

En regionsquadtree med punktdata

En algoritm av Chan hittar en disjunkt uppsättning med en storlek på minst (1 − 2/ k )·|MDS( C )| i tiden nO ^{( k ) ,} för varje konstant k > 1.

Algoritmen använder skiftade quadtrees . Algoritmens nyckelbegrepp är anpassning till quadtree-rutnätet. Ett objekt med storleken r kallas k-aligned (där k ≥ 1 är en konstant) om det är inuti en fyrträdscell med storlek som högst kr ( R ≤ kr ).

Per definition måste ett k -justerat objekt som skär gränsen för en kvadratcell av storlek R ha en storlek på minst R / k ( r > R / k ). Gränsen för en cell av storlek R kan täckas av 4 k kvadrater av storlek R / k ; därför är antalet disjunkta fettföremål som skär gränsen för den cellen högst 4 kc , där c är en konstant som mäter föremålens fethet.

Därför, om alla objekt är feta och k -justerade, är det möjligt att hitta den exakta maximala disjunkten som är inställd i tiden n ^{O ( kc )} med hjälp av en divide-and-conquer-algoritm. Börja med en quadtree-cell som innehåller alla objekt. Dela den sedan rekursivt till mindre fyrträdsceller, hitta maximum i varje mindre cell och kombinera resultaten för att få maximalt i den större cellen. Eftersom antalet osammanhängande feta objekt som korsar gränsen för varje quadtree-cell begränsas av 4 kc , kan vi helt enkelt "gissa" vilka objekt som skär gränsen i den optimala lösningen, och sedan tillämpa dela-och-härska på objekten inuti.

Om nästan alla objekt är k -justerade kan vi bara kassera de objekt som inte är k -justerade och hitta en maximal disjunkt uppsättning av de återstående objekten i tiden n ^{O ( k )} . Detta resulterar i en (1 − e ) approximation, där e är bråkdelen av objekt som inte är k -justerade.

Om de flesta objekt inte är k -justerade kan vi försöka göra dem k -justerade genom att flytta rutnätet i multipler av (1/ k ,1/ k ). Först skala objekten så att de alla finns i enhetsrutan. Betrakta sedan k skift i rutnätet: (0,0), (1/ k ,1/ k ), (2/ k ,2/ k ), ..., (( k − 1)/ k ,( k ) . − 1)/ k ). Dvs, för varje j i {0,..., k − 1}, betrakta en förskjutning av rutnätet i (j/k,j/k). Det är möjligt att bevisa att varje etikett kommer att vara 2 k -justerad för minst k − 2 värden på j . Nu, för varje j , kassera objekten som inte är k -justerade i ( j / k , j / k ) skiftet och hitta en maximal disjunkt uppsättning av de återstående objekten. Kalla den uppsättningen A ( j ). Kalla den verkliga maximala disjunktuppsättningen är A *. Sedan:

$\sum _{j=0,\ldots ,k-1}{|A(j)|}\geq (k-2)|A*|$

Därför har den största A ( j ) en storlek på minst: (1 − 2/ k )| A *|. Algoritmens returvärde är det största A ( j ); approximationsfaktorn är (1 − 2/ k ), och körtiden är n ^{O ( k )} . Vi kan göra approximationsfaktorn så liten som vi vill, så detta är en PTAS .

Båda versionerna kan generaliseras till d- dimensioner (med olika approximationsförhållanden) och till det viktade fallet.

Geometriska separatoralgoritmer

Flera dela-och-härska-algoritmer är baserade på en viss geometrisk separatorsats . En geometrisk separator är en linje eller form som separerar en given uppsättning former till två mindre delmängder, så att antalet former som förloras under uppdelningen är relativt litet. Detta tillåter både PTAS och subexponentiella exakta algoritmer, som förklaras nedan.

Feta föremål med godtyckliga storlekar: PTAS med geometriska separatorer

Låt C vara en uppsättning av n feta objekt , såsom kvadrater eller cirklar, av godtyckliga storlekar. Chan beskrev en algoritm som hittar en disjunkt uppsättning med en storlek på minst (1 − O ( √ b ))·|MDS( C )| i tiden nO ^{( b ) ,} för varje konstant b > 1.

Algoritmen är baserad på följande geometriska separatorsats, som kan bevisas på samma sätt som beviset på att det finns en geometrisk separator för disjunkta kvadrater :

För varje uppsättning C av feta objekt finns det en rektangel som delar upp C i tre delmängder av objekt – C _inuti , C _utanför och C _-gräns , så att:

|MDS( C _inuti )| ≤ a |MDS( C )|
|MDS( C _utanför )| ≤ a|MDS( C )|
|MDS( C _gräns )| c √ | MDS( C ) |

där a och c är konstanter. Om vi kunde beräkna MDS( C ) exakt, skulle vi kunna göra konstanten a så låg som 2/3 genom ett korrekt val av separatorrektangeln. Men eftersom vi bara kan approximera MDS( C ) med en konstant faktor, måste konstanten a vara större. Lyckligtvis a en konstant oberoende av | C |.

Denna separatorsats gör det möjligt att bygga följande PTAS:

Välj en konstant b . Kontrollera alla möjliga kombinationer av upp till b + 1 etiketter.

Om |MDS( C )| har en storlek på högst b (dvs alla uppsättningar av b + 1-etiketter är inte osammanhängande) så är det bara att returnera den MDS och avsluta. Detta steg tar n ^{O ( b )} tid.
Använd annars en geometrisk separator för att separera C till två delmängder. Hitta den ungefärliga MDS i C _inuti och C _utanför separat, och returnera deras kombination som den ungefärliga MDS i C .

Låt E ( m ) vara felet för ovanstående algoritm när den optimala MDS-storleken är MDS( C ) = m . När m ≤ b är felet 0 eftersom den maximala disjunktuppsättningen beräknas exakt; när m > b ökar felet med högst c √ m antalet etiketter som skärs av separatorn. Det värsta fallet för algoritmen är när uppdelningen i varje steg är i maximalt möjliga förhållande som är a :(1 − a ). Därför uppfyller felfunktionen följande återkommande relation:

E(m)=0\ \ \ \ {\text{ if }}m\leq b

E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m }}{\text{ if }}m>b

Lösningen på detta återkommande är:

E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a }}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.

dvs $E(m)=O(m/{\sqrt {b}})$ . Vi kan göra approximationsfaktorn så liten som vi vill genom ett korrekt urval av b .

Denna PTAS är mer utrymmeseffektiv än PTAS baserad på quadtrees, och kan hantera en generalisering där objekten kan glida, men den kan inte hantera det viktade fallet.

Diskar med ett begränsat storleksförhållande: exakt subexponentiell algoritm

Låt C vara en uppsättning av n skivor, så att förhållandet mellan den största radien och den minsta radien är högst r . Följande algoritm hittar MDS( C ) exakt i tiden $2^{O(r\cdot {\sqrt {n}})}$ .

Algoritmen är baserad på en breddbegränsad geometrisk separator på uppsättningen Q för mitten av alla skivor i C . Denna separatorsats gör det möjligt att bygga följande exakta algoritm:

Hitta en skiljelinje så att högst 2 n /3 centra är till höger ( C _höger ), högst 2 n / 3 centra är till vänster ( C _vänster ), och högst O ( √ n ) centra är vid en avstånd på mindre än r /2 från linjen ( C _int ).
Beakta alla möjliga icke-överlappande delmängder av C _int . Det finns högst $2^{O(r\cdot {\sqrt {n}})}$ sådana delmängder. För varje sådan delmängd beräknar du rekursivt MDS för C _vänster och MDS för C _höger och returnerar den största kombinerade mängden.

Körtiden för denna algoritm uppfyller följande återkommande relation:

T(1)=1

T(n)=2^{O (r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{ if }}n>1

Lösningen på detta återkommande är:

T(n)=2^{O(r\cdot {\sqrt {n}})}

Lokala sökalgoritmer

Pseudo-diskar: en PTAS

En pseudo-disk-set är en uppsättning objekt där gränserna för varje par av objekt skär högst två gånger (Observera att denna definition avser en hel samling och inte säger något om formerna på de specifika objekten i samlingen ). En pseudo-disk-uppsättning har en begränsad föreningskomplexitet, dvs antalet skärningspunkter på gränsen för föreningen av alla objekt är linjärt i antalet objekt. Till exempel är en uppsättning kvadrater eller cirklar av godtyckliga storlekar en pseudo-skivor-uppsättning.

Låt C vara en pseudodisk-uppsättning med n objekt. En lokal sökalgoritm av Chan och Har-Peled hittar en osammanhängande uppsättning storlek åtminstone $(1-O({\frac {1}{\sqrt {b}}}))\cdot |MDS(C)|$ i tiden $O(n^{ b+3})$ , för varje heltalskonstant $b\geq 0$ :

INITIALISERING: Initiera en tom uppsättning, $S$ .
SÖK: Slinga över alla delmängder av $CS$ $C-S$ vars storlek är mellan 1 och $b+1$ $b+1$ . För varje sådan delmängd X :
- Verifiera att X själv är oberoende (annars gå till nästa delmängd);
- Beräkna mängden Y av objekt i S som skär X .
- Om $|Y|<|X|$ , ta sedan bort Y från S och infoga X : $S:=S-Y+X$ .
END: returnera setet S .

Varje utbyte i söksteget ökar storleken på S med minst 1, och kan därför ske högst n gånger.

Algoritmen är mycket enkel; den svåra delen är att bevisa approximationsförhållandet.

Se även.

Linjär programmeringsavslappningsalgoritmer

Pseudo-diskar: en PTAS

Låt C vara en pseudodisk-uppsättning med n objekt och föreningskomplexitet u . Med hjälp av linjär programmeringsrelaxation är det möjligt att hitta en disjunkt uppsättning storlek åtminstone ${\frac {n}{u}}\cdot |MDS(C)|$ . Detta är möjligt antingen med en randomiserad algoritm som har en hög sannolikhet för framgång och körtid $O(n^{3})$ , eller en deterministisk algoritm med en långsammare körtid (men fortfarande polynom) . Denna algoritm kan generaliseras till det viktade fallet.

Andra klasser av former för vilka approximationer är kända

Linjesegment i det tvådimensionella planet.
Godtyckliga tvådimensionella konvexa objekt .
Kurvor med ett begränsat antal skärningspunkter.

externa länkar

Anteckningar