2B düzlemdeki her bir noktaya en yakın üç noktayı bulma

Question

Size düzlemdeki bir nokta listesi verilir, her bir noktayı, ona en yakın olan diğer üç noktayla birlikte gönderen bir program yazar. Bu üç nokta mesafeye göre sıralanır.

1 2,3,4 
2 1,3,4 
3 1,2,4 
4 1,2,3 
5 4,3,1 

Bu Bir:

1 0.0 0.0 
2 10.1 -10.1 
3 -12.2 12.2 
4 38.3 38.3 
5 79.99 179.99 

İşletme programı çıktılayacaktır y koordinatı x koordinatı numarası: Her bir satır formunun olduğu noktalarda verilen bir dizi Örneğin

, Bir online Forumda bulduğum görüşme sorusu. Bir O (n * n) çözümü düşünebilirim: her noktanın her bir noktaya olan mesafesini hesaplayın. Bu nokta için minimum mesafe noktalarını döndürün. Diğer noktalar için işlemi tekrarlayın

Answer 1

K-d ağacı veya dörtlü ağaç gibi uzamsal veri yapılarına bakmak isteyebilirsiniz, bu da en yakın komşu aramalar için mükemmel beklenen zaman garantileri verir. Örneğin, k-d ağacı, O (n) n ön işleme işini yaptıktan sonra O (n) en kötü durum süresi ve O (sqrt N) beklenen zamanda en yakın komşu aramalarını yapabilir. Alternatif olarak, eğer noktaların çoğunlukla rasgele dağıtıldığını biliyorsanız, boşluğu belli bir boyuttaki bir kovaya bölmeyi düşünebilirsiniz. Bir noktaya en yakın komşuları bulmak için, aynı kovadaki tüm noktalara, daha sonra yakınlardaki kovalara, vb. Tüm noktalara bakabilirsiniz. Eğer noktalar güzelse, nokta başına O (n/b) zamanına yakın olmalıdır. dağıtılmış ve b kovalar vardır.

Bu yardımcı olur umarız! Hiç ardından (nn günlük ) algoritması bir O yol açar Delaunay triangulation duyduysanız

Answer 2

Ne aradıkları olduğunu.

Düzenle. Yorumlardaki düzeltmeye göre ima ettiğim kadar basit değil. Bir O (n günlük n) zaman, ama Dickerson Drysdale ve Çuval tarafından kağıt açıklandığı gibi, biraz iş gerektirir üç yakın komşuları bulmak için Delaunay nirengi kullanabilirsiniz "Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors."