İyi ayrılmış çift ayrışımı - Well-separated pair decomposition - Wikipedia

İçinde hesaplamalı geometri, bir iyi ayrılmış çift ayrışımı (WSPD) bir dizi nokta , bir dizi çift dizisidir , öyle ki her çift iyi ayrılmışve her iki farklı nokta için , ikisini ayıran tam olarak bir çift vardır.

İyi ayrılmış bir çift ayrışımının neden olduğu grafik, bir k anahtarı of tamamlayınız Öklid grafiği ve bununla ilgili çeşitli sorunların çözümlerini tahmin etmede kullanışlıdır.[1]

Tanım

İyi ayrılmış çiftin görsel temsili

İzin Vermek iki ayrık nokta kümesi olmak , belirtmek eksen hizalı minimum sınırlayıcı kutu içindeki puanlar için , ve belirtmek ayırma faktörü.

Düşünüyoruz ki ve olmak iyi ayrılmışeğer her biri için ve var bir d-top yarıçap iki küre en az minimum mesafeye sahip olacak şekilde .[2]

İyi ayrılmış bir dizi alt küme olarak düşünürüz. , biri olmak iyi ayrılmış çift ayrışımı (WSPD) nın-nin herhangi iki farklı nokta için tam olarak bir tane var , öyle ki

  • ve veya
  • ve .[1]

İnşaat

Ağacı ayır

Bir inşa etme yoluyla adil bölünmüş ağaç boyutunda bir WSPD oluşturmak mümkündür içinde zaman.[2]

Bir nokta kümesinin bölünmüş ağacının genel prensibi S bu her düğüm mü sen Ağacın% 50'si bir dizi noktayı Ssen ve sınırlayıcı kutu R (Ssen) nın-nin Ssen en uzun kenarı boyunca iki eşit parçaya bölünmüştür ve sen ve puan seti. Sette sadece bir nokta kalana kadar özyinelemeli olarak yapılır.

İzin Vermek Lmax(R (X)) nokta kümesinin sınırlayıcı hiperdörtgenin en uzun aralığının boyutunu gösterir X ve izin ver Lben(R (X)) boyutunu belirtmek ben- nokta kümesinin sınırlayıcı hiperdörtgenin. boyutu X. Aşağıda Bölünmüş ağaç hesaplaması için sözde kod veriyoruz.

SplitTree (S)    İzin Vermek sen için düğüm ol S    Eğer | S | = 1        R (u): = R (S) // R (S) her kenarın uzunluğu sıfır olan bir hiper dikdörtgendir. Depolamak sen S'deki tek nokta Başka        Hesaplama R (S)        Bırak ben-nci boyut nerede Lmax(R (S)) = Lben(R (S))        Bölünmüş R (S) boyunca ben- iki aynı boyutlu hiperdörtgende -inci boyut ve iki set oluşturmak için bu hiperdörtgende bulunan noktaları alın Sv ve Sw.        v: = SplitTree (Sv)        w: = SplitTree (Sw)        Mağaza v ve w sırasıyla sol ve sağ çocukları sen.        R (u): = R (S)    dönüş sen

Bu algoritma çalışır zaman.

Çalışan daha verimli bir algoritma veriyoruz aşağıdaki zaman. Amaç, listeyi yalnızca özyinelemenin adımı başına işlem, ancak özyinelemeyi yalnızca her seferinde en fazla yarım noktada çağırır.

İzin Vermek Sbenj ol jkoordinatı ben-nci nokta S öyle ki S her boyut için sıralanır ve p (Sbenj) nokta olun. Ayrıca izin ver h (R (S)) en uzun kenarını bölen hiper düzlem olun R (S) ikiye. Sözde koddaki algoritma:

SplitTree (S, u)    Eğer | S | = 1        R (u): = R (S) // R (S) her kenarın uzunluğu sıfır olan bir hiper dikdörtgendir. Depolamak sen tek nokta S.    Başka        boyut: = | S |        tekrar et            Hesaplama R (S)            R (u): = R (S)            j: = 1            k: = | S |            Bırak ben-nci boyut nerede Lmax(R (S)) = Lben(R (S))            Sv : = ∅            Sw : = ∅            süre Sbenj + 1  ve Sbenk-1 > h (R (S))                beden: = beden - 1                Sv : = Sv ∪ {p (S_i ^ j)}                Sw : = Sw ∪ {p (S_i ^ k)}                j: = j + 1                k: = k - 1                        İzin Vermek v ve w sırasıyla sol ve sağ çocukları olmak sen.            Eğer Sbenj + 1 > h (R (S))                Sw : = S  Sv                u: = w                S: = Sw                SplitTree (Sv, v)            Aksi takdirde Sbenk-1                 Sv : = S  Sw                u: = v                S: = Sv                SplitTree (Sw, w)        a kadar boyut ≤n2        SplitTree (S, u)

Her düğüm için sıralı listeleri koruyabilmek için bağlantılı listeler kullanılır. Sabit zamanda bir noktayı geri alabilmek için her liste için diğerlerine çapraz işaretçiler tutulur. Yukarıdaki algoritmada, döngünün her yinelemesinde, özyinelemeye bir çağrı yapılır. Gerçekte, noktalara başvurma ek yükü olmadan listeyi yeniden oluşturabilmek için, tüm noktalar düğümlerine atandıktan sonra sıralı listeleri yeniden oluşturmak gerekir. Yeniden oluşturma işlemini yapmak için, her boyut için her liste boyunca yürüyün, her noktayı ilgili düğüm listesine ekleyin ve yeni listelere çapraz işaretçileri ekleyebilmek için orijinal listeye çapraz işaretçiler ekleyin. Son olarak, her düğüm ve kümesindeki özyinelemeyi çağırın.

WSPD hesaplaması

Sınırlayıcı kutularla hesaplanan iyi ayrılmış bir çiftin görsel temsili

WSPD, böylesi bölünmüş bir ağaçtan özyinelemeli çağrılarak çıkarılabilir. FindPairs (v, w) çocukları üzerinde işlev her bölünmüş ağaçtaki düğüm. İzin Vermek senl / senr düğümün çocuklarını gösterir sen. Pseudocode veriyoruz FindWSPD (T, s) aşağıdaki fonksiyon.

FindWSPD (T, s)    her biri için düğüm sen bu bölünmüş ağaçtaki bir yaprak değil T yapmak        FindPairs (ulsenr)

Pseudocode veriyoruz FindPairs (v, w) aşağıdaki fonksiyon.

FindPairs (v, w)    Eğer Sv ve Sw açısından iyi ayrılmışlardır s         bildiri çifti (Sv, Sw)    Başka        Eğer( Lmax(R (v)) ≤ Lmax(R (w)) ) Yinelemeli çağrı FindPairs (v, wl) ve FindPairs (v, wr)        Başka            Yinelemeli çağrı FindPairs (vl, w) ve FindPairs (vr, w)

Birleştirmek s- tüm çağrılardan iyi ayrılmış çiftler FindPairs (v, w) ayırma için WSPD'yi verir s.

Algoritmanın doğruluğunun kanıtı

Algoritma tarafından döndürülen çiftlerin, işlevin dönüş koşulu nedeniyle iyi ayrıldığı açıktır. FindPairs.

Şimdi, bunu farklı noktalar için kanıtlamamız gerekiyor. ve içinde benzersiz bir çift var böylece (i) ve veya (ii) ve . (İ) 'nin geçerli olduğu genelliği kaybetmeden varsayalım.

İzin Vermek en düşük ortak atası olmak ve bölünmüş ağaçta ve bırak ve çocukları olmak . Son varsayım nedeniyle, alt ağacında ve alt ağacında . Bir çağrı FindPairs (v, w) mutlaka yapılır FindWSPD. Çünkü, bir özyineleme olduğu her seferinde, özyineleme ağacı, geçerli özyineleme çağrısının tüm noktalarını içeren iki dal oluşturur, bir çağrı dizisi olacaktır. FindPairs sahip olmaya götüren içinde ve içinde .

Çünkü en düşük ortak atasıdır ve , arıyor FindPairs daha yüksek bir düğümün çocuklarında ve çift ​​olmamak ve aramak FindPairs alt ağaçlarından birinin düğümlerinden birindeki çocuklar üzerinde ile sonuçlanır veya herhangi bir çiftte olmamak. Böylece çifti ayıran benzersiz olan ve .

Özyineleme ağacı her ikiye bölündüğünde, ayrıştırmaya bir çift daha eklenir. Bu nedenle, algoritma çalışma zamanı, son ayrıştırmadaki çift sayısı içindedir.

Callahan ve Kosaraju, bu algoritmanın boyutta İyi Ayrılmış Çift Ayrıştırma (WSPD) bulduğunu kanıtladı. .[2]

Özellikleri

Lemma 1: İzin Vermek iyi ayrılmış bir çift olmak . İzin Vermek ve . Sonra, .

Kanıt: Çünkü ve aynı sette, bizde var nerede çevreleyen çemberin yarıçapıdır ve . Çünkü ve iki iyi ayrılmış sette, bizde . Bunu elde ederiz:

Lemma 2: İzin Vermek iyi ayrılmış bir çift olmak . İzin Vermek ve . Sonra, .

Kanıt: Üçgen eşitsizliğine göre:

Lemma 1'den şunu elde ederiz:

Başvurular

İyi ayrılmış çift ayrışımının bir dizi problemi çözmede uygulaması vardır. WSPD şu amaçlarla kullanılabilir:

  • Çöz en yakın çift sorunu içinde zaman.[1]
  • Çöz ken yakın çift problemi zaman.[1]
  • Çöz ken yakın çift problemi zaman.[3]
  • Çöz en yakın komşular sorunu içinde zaman.[1]
  • Sağlayın -yaklaşım of çap belirlenen bir noktanın zaman.[1]
  • Doğrudan bir t anahtarı bir nokta kümesinin.[1]
  • Bir t-yaklaşımı sağlayın Öklid asgari kapsayan ağaç d boyutlarında zaman.[1]
  • Sağlayın -yaklaşıklığı Öklid asgari kapsayan ağaç d boyutlarında zaman.[4]

Referanslar

  1. ^ a b c d e f g h Smid, Michiel (16 Ağustos 2005). "İyi ayrılmış çift ayrışımı ve uygulamaları" (PDF). Alındı 26 Mart 2014.
  2. ^ a b c Callahan, P. B. & Kosaraju, S.R. (Ocak 1995). "K-En Yakın Komşulara ve n-Vücut Potansiyel Alanlarına Uygulamalar ile Çok Boyutlu Nokta Kümelerinin Ayrışımı". ACM Dergisi. 42 (1): 67–90. doi:10.1145/200836.200853.
  3. ^ Bespamyatnikh, Sergei; Segal, Michael (2002). "Yaklaşık Mesafeler için Hızlı Algoritmalar". Algoritma. 33 (2): 263–269. doi:10.1007 / s00453-001-0114-7.
  4. ^ Arya, Sunil; Dağı, David M. (2016). "Yaklaşık öklid minimum kapsayan ağaçları hesaplamak için hızlı ve basit bir algoritma". Yirmi Yedinci Yıllık ACM-SIAM Ayrık Algoritmalar Sempozyumu Bildirileri.