Geometrisk separator

En geometrisk separator är en linje (eller annan form) som delar upp en samling geometriska former i två delmängder, så att andelen former i varje delmängd är avgränsad, och antalet former som inte tillhör någon delmängd (dvs. av separatorn själv) är liten.

När en geometrisk separator finns kan den användas för att bygga dela-och-härska-algoritmer för att lösa olika problem inom beräkningsgeometri .

Separatorer som är linjer

Generell fråga

1979 ställde Helge Tverberg följande fråga. För två positiva heltal k , l , vilket är det minsta talet n ( k , l ) så att det för varje familj av parvis disjunkta konvexa objekt i planet finns en rät linje som har minst k objekt på ena sidan och åtminstone jag på andra sidan?

Följande resultat är kända.

• Uppenbarligen är n (1,1)=1.
• Hope och Katchalski bevisade att n ( k ,1) ≤ 12( k -1) för alla k ≥ 2.
• Villanger bevisade att n(2,2) = ∞: han visade en oändlig familj av parvis disjunkta segment så att ingen rät linje har två segment på varje sida. Pach och Tardos visade en enklare konstruktion med endast enhetssegment och en annan konstruktion med enbart skivor (eller kvadrater).

Separatorer för axlar-parallella rektanglar

Givet en uppsättning av N =4 k disjunkta axelparallella rektanglar i planet, finns det en linje, antingen horisontell eller vertikal, så att åtminstone N /4 rektanglar ligger helt på varje sida om den (därav högst N /2 rektanglar skärs av separatorlinjen).

Bevis

Definiera W som den mest västliga vertikala linjen med minst N /4 rektanglar helt i väster. Det finns två fall:

• Om det finns åtminstone N /4 rektanglar helt öster om W , så är W en vertikal separator.
• Annars, genom att flytta W något åt ​​väster, får vi en vertikal linje som skär mer än N /2 rektanglar. Hitta en punkt på denna linje som har minst N /4 rektanglar ovanför och N /4 rektanglar under sig, och rita en horisontell avgränsare genom den.

Optimalitet

Antalet korsade former, garanterat av ovanstående sats, är O( N ). Denna övre gräns är asymptotiskt snäv även när formerna är fyrkantiga, som illustreras i figuren till höger. Detta står i skarp kontrast till den övre gränsen för O( √ N ) skärande former, vilket garanteras när separatorn är en sluten form (se föregående avsnitt ).

Dessutom, när formerna är godtyckliga rektanglar, finns det fall där ingen linje som skiljer mer än en enda rektangel kan korsa mindre än N /4 rektanglar, som illustreras i figuren till höger.

Generaliseringar

Ovanstående sats kan generaliseras från disjunkta rektanglar till k -tjocka rektanglar. Dessutom, genom induktion på d , är det möjligt att generalisera ovanstående sats till d-dimensioner och få följande sats:

Givet N -axelparallella d -boxar vars inre är k -tjocka, finns det ett axelparallellt hyperplan så att åtminstone:

$\lfloor (N+1) -k)/(2d)\rgolv$

av d -boxens inre ligger på vardera sidan av hyperplanet.

För specialfallet när k = N − 1 (dvs varje punkt finns i högst N − 1 rutor), gäller följande sats:

Givet N -axelparallella d -boxar vars inre är ( N − 1)-tjocka, finns det ett axelparallellt hyperplan som skiljer två av dem åt.

Objekten behöver inte vara lådor och separatorerna behöver inte vara axelparallella:

Låt C vara en samling möjliga orienteringar av hyperplan (dvs C = {horisontell,vertikal}). Givet N d -objekt, så att vartannat osammanhängande objekt separeras av ett hyperplan med en orientering från C , vars inre är k -tjocka, finns det ett hyperplan med en orientering från C så att åtminstone: ( N + 1 − k )/O( C ) av d -objektens inre ligger helt på var sida om hyperplanet.

Algoritmiska versioner

Det är möjligt att hitta hyperplanen som garanteras av ovanstående satser i O( Nd ) steg. Dessutom, om 2d - listorna med de nedre och övre ändpunkterna för intervallen som definierar rutornas i :te koordinater är försorterade, kan det bästa sådana hyperplanet (enligt en mängd olika optimalitetsmått) hittas i O( Nd ) steg.

Separatorer som är slutna former

Ett enkelt fall där en separator garanterat finns är följande:

Givet en uppsättning av n disjunkta axelparallella kvadrater i planet, finns det en rektangel R så att högst 2 n /3 av kvadraterna är inuti R , högst 2 n /3 av kvadraterna är utanför R , och vid de flesta O(sqrt( n )) av kvadraterna är inte innanför och inte utanför R (dvs. skär gränsen för R ).

Således är R en geometrisk separator som separerar de n kvadraterna i två delmängder ("inuti R " och "utanför R "), med en relativt liten "förlust" (rutorna som skärs av R anses "förlorade" eftersom de inte hör hemma till någon av de två delmängderna).

Bevis

Definiera en 2-fat rektangel som en axelparallell rektangel med ett bildförhållande på högst 2.

₀₀ Låt R vara en rektangel med minimal area med 2 fetter som innehåller mitten av minst n /3 rutor. Sålunda innehåller varje 2-fettsrektangel mindre än R färre än n /3 rutor.

₀ För varje t i [0,1), låt _Rt vara en 2-fettsrektangel med samma centrum som R , uppblåst med 1 + t .

• Rt innehåller R , så det innehåller mitten av minst n /3 rutor _{. 0}
• ₀₀ R _t är mindre än dubbelt så stor som R , så den kan täckas av två 2-fettiga rektanglar som är mindre än R . Var och en av dessa 2-fettiga rektanglar innehåller mitten av mindre än n /3 rutor. Därför R _t mitten av mindre än 2 n /3 kvadrater.

Nu återstår att visa att det finns ett t för vilket R _t högst skär O(sqrt( n )) kvadrater.

₀₀ Tänk först på alla "stora rutorna" – rutorna vars sidolängd är minst $\operatorname {width} (R_{0})/2{\sqrt {n}}$ . För varje t är omkretsen av R _t högst 2·perimeter( R ) vilket är högst 6·width( R ), så den kan skära högst $12{\sqrt {n}}$ stor rutor.

Ta sedan hänsyn till alla "små rutor" – rutor vars sidolängd är mindre än $\operatorname {width} (R_{0})/2{\sqrt {n}}$ .

För varje t , definiera: intersect( t ) som mängden små kvadrater som skärs av gränsen för R _t . För varje t ₁ och t ₂ , om ${\displaystyle |t_{1}-t_{2}|\geq 1/{\sqrt {n}}} ,$ sedan $|\operatörsnamn {width} (R_{t_{1}})-\operatörsnamn {width} (R_{t_{2}})|\geq \operatörsnamn {width} ( R_{0})/{\sqrt {n}}$ . Därför finns det ett gap på åtminstone $\operatorname {width} (R_{0})/2{\sqrt {n}}$ mellan gränsen för R _{t 1} och gränsen av Rt2 . _{_ _} Därför är intersect( t ₁ ) och intersect( t ₂ ) disjunkta. Därför:

$\sum _{j=0}^{{\sqrt {n}}-1}{|\operatörsnamn {skärning} (j/{\sqrt {n}})|}\leq n$

₀ finns det enligt duvhålsprincipen ett visst j för vilket:

$|\operatörsnamn {skärning} (j_{0}/{\sqrt {n}})|\leq {\sqrt {n}}$

Separatorn vi letar efter är rektangeln R _t , där $t=j_{0}/{\sqrt {n}}$ .

Applikationsexempel

Med hjälp av denna separatorsats kan vi lösa vissa problem inom beräkningsgeometri på följande sätt:

• Separera den ingående uppsättningen av kvadrater till två disjunkta delmängder;
• Lös problemet för varje delmängd separat;
• Kombinera lösningarna på de två delproblemen och få en ungefärlig lösning på det ursprungliga problemet.

Generaliseringar

Ovanstående sats kan generaliseras på många olika sätt, med möjligen olika konstanter. Till exempel:

• Istället för rutor kan inmatningssamlingen innehålla godtyckliga feta objekt , såsom: cirklar, rektanglar med ett begränsat bildförhållande, etc.
• Istället för tvådimensionella former i ett plan kan indatasamlingen innehålla objekt av vilken dimension som helst, och de kan placeras i en d -dimensionell torus .
• Istället för att kräva att formerna i ingångssamlingen är osammanhängande kan vi ställa ett svagare krav, att samlingen är:
  • k-tjock , dvs varje punkt är täckt av högst k olika former.
  • lk-tjock , dvs varje punkt är täckt av högst k olika former med ett storleksförhållande (storlek på största form dividerat med storlek på minsta form) högst l .
  • k-overloaded , dvs för varje undersamling av former är summan av deras individuella mått högst k gånger måttet på deras förening.
• Istället för en rektangelavskiljare kan avskiljaren vara vilken form som helst som kan täckas av mindre kopior av sig själv.
• Istället för att begränsa antalet former på varje sida av separatorn, är det möjligt att begränsa vilket mått som helst som uppfyller vissa axiom.

Optimalitet

Förhållandet 1:2, i kvadratseparatorsatsen ovan, är det bästa som kan garanteras: det finns samlingar av former som inte kan separeras i ett bättre förhållande med en separator som bara korsar O(sqrt( n )) former . Här är en sådan samling (från sats 34 av ):

Betrakta en liksidig triangel . Vid var och en av dess 3 hörn, sätt N /3 former arrangerade i en exponentiell spiral, så att diametern ökar med en konstant faktor varje varv av spiralen, och varje form berör sina grannar i spiralordningen. Börja till exempel med en 1-för-Φ rektangel, där Φ är det gyllene snittet . Lägg till en intilliggande Φ-för-Φ-ruta och få ytterligare en gyllene rektangel. Lägg till en intilliggande (1+Φ)-by-(1+Φ) kvadrat och få en större gyllene rektangel, och så vidare.

Nu, för att separera mer än 1/3 av formerna, måste separatorn separera O( N ) former från två olika hörn. Men för att göra detta måste separatorn skära O( N )-former.

Separatorer som är breddavgränsade remsor mellan parallella hyperplan

Låt Q vara en uppsättning av n punkter i planet så att det minimala avståndet mellan punkter är d . Låt a >0 vara en konstant.

Det finns ett par parallella linjer med avstånd a , så att högst 2 n /3 punkter ligger på varje sida av remsan, och högst $1,3{a \over d}{\sqrt {n }}$ punkter ligger inuti remsan.

Motsvarande: det finns en linje så att högst 2 n /3 punkter ligger på varje sida om den och högst $1,3{a \over d}{\sqrt {n}}$ punkter ligger vid en avstånd på mindre än en /2 från den.

Bevisskiss

Definiera Q: s mittpunkt som en punkt o så att varje linje genom den har högst 2 n /3 punkter av Q på varje sida av den. Förekomsten av en mittpunkt kan bevisas med hjälp av Hellys sats .

För en given punkt p och konstant a >0, definiera Pr(a,p,o) som sannolikheten att en slumpmässig linje genom o ligger på ett avstånd som är mindre än a från p . Tanken är att binda denna sannolikhet och därmed binda det förväntade antalet punkter på ett avstånd mindre än a från en slumpmässig linje genom o . Sedan, enligt duvhålsprincipen , är åtminstone en linje genom o den önskade separatorn.

Ansökningar

Separatorer med begränsad bredd kan användas för att ungefär lösa problemet med proteinveckningsproblem . Den kan också användas för en exakt subexponentiell algoritm för att hitta en maximal oberoende uppsättning, såväl som flera relaterade täckningsproblem, i geometriska grafer.

Geometriska separatorer och plana grafseparatorer

Planarseparatorsatsen kan bevisas genom att använda cirkelpackningssatsen för att representera en plan graf som kontaktgrafen för ett system av skivor i planet, och sedan genom att hitta en cirkel som bildar en geometrisk separator för dessa skivor .

Se även

• Ham sandwich-sats : givet n mätbara objekt i n -dimensionellt utrymme är det möjligt att dela dem alla på mitten (med hänsyn till deras mått, dvs volym) med ett enda ( n − 1)-dimensionellt hyperplan.
• Giljotinseparation : problemet med att separera konvexa föremål i planet med hjälp av giljotinsnitt.
• Andra separationssatser .
• Samtidig separator: en separator som samtidigt separerar formerna i flera samlingar, samtidigt som den skär ett litet antal former i varje samling, kanske inte alltid finns.