Väl separerade parsönderdelning

Inom beräkningsgeometri är en välseparerad parupplösning (WSPD) av en uppsättning punkter $R} ^{d}}$$(A_{i},B_{i})$ en sekvens av par av mängder , så att varje par är väl separerade och för varje två distinkta punkter $p,q\in S$ , det finns exakt ett par som skiljer de två åt.

Grafen som induceras av en väl separerad parsönderdelning kan fungera som en k-nyckel för den kompletta euklidiska grafen och är användbar för att approximera lösningar på flera problem som hänför sig till detta.

Definition

Visuell representation av väl separerade par

Låt $A,B$ vara två disjunkta uppsättningar av punkter i $\mathbb {R} ^{d}$ , $R(X)$ betecknar axeln- aligned minimum bounding box för punkterna i $X$ och $s>0$ anger separationsfaktorn .

Vi anser att $A$ och $B$ är väl separerade , om för var och en av $R(A)$ och $R(B)$ det finns en d-kula med radien $\rho$ som innehåller den, så att de två sfärerna har ett minsta avstånd på minst $s\rho$ .

Vi betraktar en sekvens av väl separerade par av delmängder av $S$ , ${\displaystyle (A_{ 1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})} för att vara en välseparerad parupplösning ($ WSPD ) av ${ \displaystyle S}$ om för två distinkta punkter $p,q\in S$ , finns det exakt en ${\displaystyle i} ,$ 1 $\displaystyle 1\leq i\ leq m}$ , sådan att antingen

• $p\in A_{i}$ och $q\in B_{i}$ , eller
• $q\in A_{i}$ och $p\in B_{i}$ .

Konstruktion

Delat träd

Genom att konstruera ett rättvist delat träd är det möjligt att konstruera en WSPD med storleken $O(s^{d}n)$$O( n\lg n)$ O tid.

Su _Den allmänna principen för det delade trädet för en punktmängd S är att varje nod u i trädet är _{representerar} en uppsättning punkter och att begränsningsrutan R(Su ₎ för Su delad längs sin längsta sida i två lika delar som bildar u två barn och deras poängmängd. Det görs rekursivt tills det bara finns en punkt i setet.

Låt L _max (R(X)) _beteckna Li (R(X)) storleken på det längsta intervallet för den gränsande hyperrektangeln för punktmängden X och låt beteckna storleken på den i -te dimensionen av den gränsande hyperrektangeln för punktmängden X . Vi ger pseudokod för beräkningen av Split-trädet nedan.

     
        
        
      SplitTree(S)  Låt  u  vara noden för  S  om  |S| = 1   R(u) := R(S)  //  R(S)  är en hyperrektangel där varje sida har längden noll. Lagra i   u  den enda punkten i S.  annars  Beräkna  R(S)  Låt den  i  -te dimensionen vara den där  L  max  (R(S)) = L  i  (R(S))  Dela  R(S)  längs i:  et  -th dimensionen i två lika stora hyperrektanglar och ta punkterna i dessa hyperrektanglar för att bilda de två uppsättningarna  S  v  och  S  w  .  v := SplitTree(S  v  )  w := SplitTree(S  w  )  Lagra  v  och  w  som vänster och höger barn till  u  .  R(u) := R(S)  returnerar  u 

Denna algoritm körs i $O(n^{2})$ tid.

Vi ger en mer effektiv algoritm som körs i $O(n\lg n)$ tid nedan. Målet är att loopa över listan i endast $O(n)$ operationer per steg av rekursionen men bara kalla rekursionen på högst hälften av poängen varje gång.

Låt Si _j ⁾ vara den i :te koordinaten för den p(Si _j ^j te : punkten i S så att Si _. sorteras enligt den i: te koordinaten och är punkten Låt också h(R(S)) vara hyperplanet som delar den längsta sidan av R(S) i två delar. Här är algoritmen i pseudokod:

     
        
        
        
            
            
            
            
            
               
                
                
                 
                
                
                
                
             
                
                
                
                
         
         SplitTree(S, u)  om  |S| = 1   R(u) := R(S)  //  R(S)  är en hyperrektangel där varje sida har längden noll. Lagra i   u  den enda punkten i  S  .  annan  storlek := |S|  upprepa  Beräkna  R(S)  R(u) := R(S)  j : = 1  k : = |S|  Låt den  i  -te dimensionen vara den där  L  max  (R(S)) = Li  (  R(S))  S  v  : = ∅  S  w  : = ∅  medan  S  i  j+1  < h(R(S) )  och  S  i  k-1  > h(R(S))  storlek := storlek - 1  S  v  : = S  v  ∪ {p(S_i^j)  }  S  w  : = S  w  ∪ {p(S_i^k)  }  j := j + 1  k := k - 1  Låt  v  och  w  vara respektive vänster och höger barn till  u  .  om  S  i  j+1  > h(R(S))  S  w  := S \ S  v  u := w  S := S  w  SplitTree(S  v  ,v)  annars om  S  i  k-1  < h(R( S))  S  v  := S \ S  w  u := v  S := S  v  SplitTree(S  w  ,w)  tills 
 storlek ≤  n  ⁄  2  SplitTree(S,u) 

För att kunna underhålla de sorterade listorna för varje nod används länkade listor. Korspekare hålls för varje lista till de andra för att kunna hämta en punkt i konstant tid. I algoritmen ovan, i varje iteration av loopen, görs ett anrop till rekursionen. I verkligheten, för att kunna rekonstruera listan utan att behöva tillgripa poängen, är det nödvändigt att bygga om de sorterade listorna när alla punkter har tilldelats deras noder. För att göra ombyggnaden, gå längs varje lista för varje dimension, lägg till varje punkt i motsvarande lista med dess noder och lägg till korspekare i den ursprungliga listan för att kunna lägga till korspekare för de nya listorna. Till sist, anropa rekursionen på varje nod och hans uppsättning.

WSPD-beräkning

Visuell representation av ett väl separerat par beräknat med begränsningsrutorna

WSPD kan extraheras från ett sådant delat träd genom att anropa den rekursiva FindPairs(v,w) -funktionen på barnen i varje nod i det delade trädet. Låt u _l / u _r beteckna barnen i noden u . Vi ger pseudokod för FindWSPD(T, s) -funktionen nedan.

  FindWSPD(T, s)  för varje  nod  u  som inte är ett löv i det delade trädet  T  do  FindPairs(  ul  , u  r  ) 

Vi ger pseudokod för FindPairs(v, w) -funktionen nedan.

 
    
        
         FindPairs(v, w)  och  om  Sv  S  w  är  väl separerade med avseende på  s  rapportpar  (S  v  , S  w  )  annars  om  (  L  max  (R(v)) ≤ L  max  (R(w))  ) Anropa  FindPairs(v, w  l  )  och  FindPairs(v, w  r  )  rekursivt  annars anropa   FindPairs(v  l  , w)  och  FindPairs(v  r  , w) rekursivt. 

Kombination av de s -väl separerade paren från alla anrop av FindPairs(v,w) ger WSPD för separation s .

Bevis på korrekthet av algoritmen

Det är tydligt att paren som returneras av algoritmen är väl separerade på grund av returvillkoret för funktionen FindPairs . Nu måste vi bevisa att för alla distinkta punkter $\{A,B \}$$\displaystyle p}$ och $q$ i $S$ finns det ett unikt par så att (i) $p\in A$ och $q\in B$ eller (ii) $p\in B$ och $q\in A$ . Antag utan förlust av allmänhet att (i) gäller. Låt $u$ vara den lägsta gemensamma förfadern till $p$ och $q$ i det delade trädet och låt $v$ och $w$ vara barn till $u$ . På grund av det sista antagandet $p$ i underträdet till $v$ och $q$ i underträdet till $w$ . Ett anrop till FindPairs(v,w) görs nödvändigtvis i FindWSPD . Eftersom, varje gång det finns en rekursion, skapar rekursionsträdet två grenar som innehåller alla punkter i det aktuella rekursionsanropet, kommer det att finnas en sekvens av anrop till FindPairs som leder till att ha $p$ i $A$ och $q$ i $B$ . Eftersom $u$ är den lägsta gemensamma förfadern till $p$ och $q$ , skulle anrop av FindPairs på barnen i en högre nod resultera av $p$ och $q$ att inte vara i ett par och anropa FindPairs på barnen i en av noderna i ett av underträden till $u$ skulle resultera i att $p$ eller $q$ inte finns i någon par. Således är paret $\{A,B\}$ det unika som skiljer $p$ och $q$ .

Varje gång rekursionsträdet delas i två läggs ytterligare ett par till nedbrytningen. Så, algoritmens körtid är i antalet par i den slutliga nedbrytningen.

Callahan och Kosaraju bevisade att denna algoritm hittar en välseparerad parupplösning (WSPD) av storleken $O(s^{d}n)$ .

Egenskaper

Lemma 1 : Låt $\{A,B\}$ vara ett väl separerat par med avseende på $s$ . Låt $p,p'\in A$ och $q\in B$ . Sedan, $|pp'|\leq (2/s)|pq|$ .

Bevis : Eftersom $p$ och $p'$ är i samma uppsättning, har vi att $|pp'|\leq 2\rho$ där $\rho$ är radien för den omgivande cirkeln av $A$ och $B$ . Eftersom $p$ och $q$ är i två väl separerade uppsättningar, har vi att $|pq|\geq s\rho$ . Vi får det:

${\begin{aligned}&{\frac {|pp'|}{2}}\leq \rho \leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&{ \frac {|pp'|}{2}}\leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&|pp'|\leq {\frac {2}{s}} |pq|\\\end{aligned}}$

Lemma 2 : Låt $\{A,B\}$ vara ett väl separerat par med avseende på $s$ . Låt $p,p'\in A$ och $q,q'\in B$ . Sedan, $|p'q'|\leq (1+4/s)|pq|$ .

Bevis : Genom triangelolikheten har vi:

$|p'q'|\leq |p'p|+|pq|+|qq'|$

Från Lemma 1 får vi:

${\begin{aligned}|p'q'|&\leq (2/s)|pq|+|pq|+(2/s)|pq|\\&=(1+4/s) |pq|\end{aligned}}$

Ansökningar

Den väl separerade parsönderdelningen kan användas för att lösa ett antal problem. WSPD kan användas för att:

• Lös problemet med närmaste par i $O(n\lg n)$ tid.
• Lös problemet med k -närmaste par i $O(n\lg n+k)$ tid.
• Lös problemet med k -närmaste par i $O(n\lg n)$ tid.
• Lös problemet med alla närmaste grannar på $O(n\lg n)$ tid.
• Ange en $(1-\epsilon )$ - approximation av diametern för en punkt satt i $O(n\lg n)$ tid.
• Inducera direkt en t-nyckel av en punktuppsättning.
• Ge en t-approximation av det euklidiska minimumspännande trädet i d dimensioner i $O(n\lg n)$ tid.
• Ange en $(1+\epsilon )$ -approximation av det euklidiska minimumspännande trädet i d dimensioner i ${ \ displaystyle O(n\lg n+(\epsilon ^{-2}\lg ^{2}{\frac {1}{\epsilon }})n)} tid$ .