Soru En uzak iki nokta nasıl bulunur?


Bu, bir süre önce bir iş görüşmesinde sorulduğum bir sorudur. Ve hala mantıklı cevabı çözemiyorum.

Soru şu ki:

size puan seti verilir (x, y). En uzak 2 noktayı bulun. Birbirinden uzak.

Örneğin, puanlar için: (0,0), (1,1), (-8, 5) - en uzak olanlar: (1,1) ve (-8,5) çünkü aralarındaki mesafe daha büyüktür. her ikisi (0,0) - (1,1) ve (0,0) - (- 8,5).

Açık yaklaşım, tüm noktalar arasındaki tüm mesafeleri hesaplamak ve maksimum değeri bulmaktır. Sorun, büyük veri kümeleri için onu pahalı bir hale getiren O (n ^ 2) olmasıdır.

Sınırda bulunan ilk izleme noktaları ile yaklaşma ve daha sonra sınırların üzerinde "içeriden" daha az puan olacak, ama yine de pahalı olduğu ve en kötü durum senaryosunda başarısız olacağı varsayımıyla, bunlar için mesafeleri hesaplamaktır.

Web'de arama yapmaya çalıştı, ancak mantıklı bir cevap bulamadı - ancak bu sadece arama becerilerimden yoksun olabilir.


43
2018-04-29 09:53


Menşei


Bir saat sonra "bir süre önce" miydi? ;-) - Marcelo Cantos
Sıralamayı O (nlogn) içinde yapabilirseniz, kullanmayı deneyin. - Gabriel Ščerbák
Ne demek istiyorsun Gabriel? Neye göre sırala? - Marcelo Cantos
Çok boyutlu bir alanı "sıralayamazsınız" ya da daha doğrusu, onu birçok farklı şekilde sıralayabilirsiniz. - fortran
@Marcelo - hayır. 3 yıla yakın.


Cevaplar:


EDIT: Bir yol dışbükey bulmaktır   gövde    http://en.wikipedia.org/wiki/Convex_hull   puan kümesinin ve sonra iki   uzak noktalar bunun köşe noktalarıdır.

Muhtemelen burada cevaplandı: Algoritma birbirinden en uzak iki nokta bulmak

Ayrıca:


18
2018-04-29 10:06



Bu sorular hesaplamalı geometri değil, grafik algoritmaları ile ilgili değil mi? - P Shved
Sorunu tam bir ağırlıklı grafik olarak modelleyebilirsiniz - jk.
iyi cevap, beğeniyorum. - ldog


Sınır noktası algoritmaları boldur (konveks hull algoritmalarını arayın). Oradan, en uzak mesafeleri bulmak için O (N) zamanını almalı.

Yazarın yorumundan: ilk önce gövdede herhangi bir zıt nokta bulun ve ardından yarı-kilit adımında dolaşın. Kenarlar arasındaki açılara bağlı olarak, ya bir yürüteç ya da diğerini ilerletmek zorunda kalacaksınız, ancak gövdeyi çevrelemek için daima O (N) 'yi alacak.


8
2018-04-29 10:04



Şimdi verilen tüm N noktalarının dışbükey gövdede olduğunu varsayalım. Hala açık)? - P Shved
Yine de, yorumunuz bu sayfada doğru bir algoritmanın en iyi açıklamasıdır, bu yüzden bunu cevap metnine koyacağım ve daha sonra destekleyeceğim. - P Shved
Teşekkürler Pavel! Bu arada, hiç tereddüt etmemeye çalışmıyorum (son yorumum niyet ettiğimden daha kötü okur). Bu doğru bir şekilde elde etmek için oldukça karmaşık bir geometri ve kenar durumları. - Marcelo Cantos
@Marcelo, oh, hesaplama geometrisinde "tam algoritma" demek genellikle "sıkılmadan önce olabildiğince eksiksiz" anlamına gelir. - P Shved
Bunun bir adı var: en.wikipedia.org/wiki/Rotating_calipers - Rafał Dowgird


Tüm noktaların ortalamasını bulun, tüm noktalar ve ortalama arasındaki farkı ölçün, noktayı ortalamadan en uzak mesafeye taşıyın ve en uzak noktayı bulun. Bu noktalar dışbükey gövdenin ve en uzak iki noktanın mutlak köşeleri olacak. Son zamanlarda bunu rastgele yönlendirilmiş sonsuz düzlemlere hapsedilen dışbükey gövdelere ihtiyaç duyan bir proje için yaptım. Harika çalıştı.


6
2018-03-10 18:27



Bunun benim gibi matematik dahileri olmayan insanlar için en anlaşılabilir olduğunu düşünüyorum. Teşekkürler - Tjebo
Bunun doğru olduğunu varsayarak, bu sorunun en iyi cevabı budur (IMO), çünkü O (n), 3 boyutta genelleştirilebilir ve uygulanması önemsiz olacaktır. - Garrett Gutierrez
Bu algoritma çalışmıyor. Şu noktalarla deneyin: (-10, 0), (100, 0), (0, 70), (0, -70). Ortalamadan en uzak nokta (100, 0), fakat en uzak iki nokta (0, 70) ve (0, -70). - lvella


Bu soru Algoritmaya Giriş bölümünde tanıtıldı. Bahsedilen 1) Convex Hull O (NlgN) hesaplayın. 2) Convex Hull üzerinde M vectex varsa. O zaman en uzak çifti bulmak için O (M) 'ye ihtiyacımız var.

Bu yararlı bağlantıları buluyorum. Algoritma ayrıntılarının ve programın analizini içerir. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Bu yararlı olacaktır isterdim.


3
2017-09-25 02:39





Bir dizi noktanın çapını hesaplamak için bir algoritma arıyorsanız, Çapı (S). Bunun S'nin dışbükey gövdesinin çapı ile aynı olduğu gösterilebilir. Diam (S) = Diam (CH (S)). İlk önce kümenin dışbükey gövdesini hesaplayın.

Şimdi dışbükey gövdede tüm antipodal noktaları bulmalı ve çifti maksimum mesafeyle seçmelisin. Var O (n) dışbükey poligonda antipodal noktalar. Yani bu bir O (n lg n) en uzak noktaları bulmak için algoritma.

Bu teknik olarak bilinir Dönen Kaliperler. Marcelo Cantos'un cevabında anlattığı şey budur.

Algoritmayı dikkatli bir şekilde yazarsanız, hesaplama açıları olmadan da yapabilirsiniz. Ayrıntılar için bunu kontrol edin URL.


2
2017-11-28 16:55





En uzak çifti bulmak için stokastik bir algoritma olurdu

  • Rastgele bir nokta seçin
  • En uzak noktaya gelin
  • Birkaç kez tekrarla
  • Ziyaret edilen tüm noktaları kaldır
  • Başka bir rastgele nokta seçin ve birkaç kez tekrarlayın.

"Birkaç kez" önceden belirlediğiniz sürece, O (n) 'desınız, ancak en uzak çifti bulmayı garanti etmiyorsunuz. Ancak puan setinize bağlı olarak sonuç oldukça iyi olmalıdır. =)


1
2018-04-29 10:20



Bunu düşünün, sonra cevabınızı düzeltin ya da silin, böylelikle downvotes alamayın: neredeyse kare bir puan setiniz olduğunu hayal edin, {A=(0, 0), B=(10, 10), C=(10, 0), D=(0, 11)}; En uzak noktalar BD'dir (mesafe = 14.86); fakat A veya B'de başlamayı denerseniz, C (AC = BC = 10) veya D'yi (AD = 11, BD = 10.05) kaldırmayı cazip hissedersiniz, çünkü seçilen tepe noktasından karşı köşeye göre daha yakındırlar ( AC = 14.14), gerçekte en uzun mesafe gerçekten 14.86 . - ANeves
@sr pt: Örneğinizde, CD BD değil en uzak noktalar. A veya B'den başlayarak her zaman diğeri 2. adımda diğerini seçebilir, bu yüzden sadece bu ikisi 4. adımda kaldırılır. - Jens


Sadece birkaç düşünce:

Sadece sayıları azaltmak için puan kümenizin dışbükey gövdesini tanımlayan noktalara bakabilirsin ... ama yine de biraz "optimal değil" gibi görünüyor.

Aksi halde, puan kümeleri arasındaki bazı mesafeleri hızlıca bağlamak ve verilerinizin büyük bölümlerini ortadan kaldırmak için tekrarlanan dörtlü / sekiz ağaçlı bir yaklaşım olabilir.


0
2018-04-29 10:05





Bir başlangıç ​​noktası, incelenen en yakın nokta sorunlarına bakabilir. Vikipedi bazı seçenekleri listeler:

http://en.wikipedia.org/wiki/Closest_point_query


0
2018-04-29 10:07



Veya en.wikipedia.org/wiki/Closest_pair_problem - zaf
Eh, en yakın taban için çözümler bölmek ve fethetmek, ve en uzak noktaları bulmak için nasıl uygulayacağımı bilmiyorum.


Noktalar Kartezyen koordinatlarda verilirse bu kolay görünüyor. O kadar kolay ki, bir şeye baktığımdan eminim. Neyi kaçırdığımı göstermekten çekinme!

  1. X, y ve z koordinatlarının maksimum ve min değerlerini içeren noktaları bulunuz (toplam 6 puan). Bunlar tüm sınır noktalarının en "uzak" olmalıdır.
  2. Tüm mesafeleri hesaplayın (30 benzersiz mesafe)
  3. Maksimum mesafeyi bul
  4. Bu maksimum mesafeye karşılık gelen iki nokta, aradığınızlardır.

0
2017-08-01 17:02



Açıkçası O (N) btw ... - Justin Henrie
Tamam, daha sonra düşündüm sonra bu iki en uzak noktaları bulmak için garanti değildir. Doh! Bununla birlikte, size nokta dizilimi tarafından belirlenen bölgenin minimum boyutunu verir, bu da sqrt (2) 'den daha fazla bir ölçek ile aşılmayacaktır. Faydalı olabilir! - Justin Henrie


Bir dizi ({x1, y1), (x2, y2) ... (xn, yn) noktasını dikkate alarak, en uzak 2 noktayı bul.

Benim yaklaşımım:

1). Bir referans noktasına (xa, ya) ihtiyacınız var ve şöyle olacak:
xa = (x1 + x2 + ... + xn) / n
ya = (y1 + y2 + ... + yn) / n

2). Noktadan (xa, ya) (x1, y1), (x2, y2), ... (xn, yn) arasındaki tüm mesafeleri hesaplayın
İlk "en uzak nokta" (xb, yb) maksimum mesafeye sahip olanıdır.

3). Noktadan (xb, yb) ile (x1, y1), (x2, y2), ... (xn, yn) arasındaki tüm mesafeleri hesaplayın.
Diğer "en uzak nokta" (xc, yc) maksimum mesafeye sahip olanıdır.

Yani en uzak noktalarınızı (xb, yb) (xc, yc) O (n) olarak aldınız

Örneğin, puan için: (0,0), (1,1), (-8, 5)

1). Referans noktası (xa, ya) = (-2.333, 2)

2). Mesafeleri hesaplayın:
(-2.333, 2) ila (0,0): 3,073 arası
(-2.333, 2) ila (1,1) arası: 3.480
(-2.333, 2) ila (-8, 5) arasında: 6.411
Yani ilk en uzak nokta (-8, 5)

3). Mesafeleri hesaplayın:
(-8, 5) ila (0,0) arası: 9.434
(-8, 5) ila (1,1) arası: 9.849
(-8, 5) ila (-8, 5) arasında: 0
Yani diğer en uzak nokta (1, 1)


-1
2017-09-07 04:43



ilk önce bunun neden doğru olduğunu kanıtlamadığınızı, ancak bunun yanlış olduğunu gösteren bir örnek var {{0, 0}, {10,0}, {- 10,0}, {0,17}} doğru cevap 20 , cevabın ~ 19.72 - Vladp


A - (x1, y1), B- (x2, y2) dik açı üçgenlerine bakın ve a / B mesafesi b / w = [x (| x1 | + | x2 |) ^ 2 + (| y1 | + | y2 |) ^ 2]


-2
2017-11-15 13:59



Zaten bunların arasındaki mesafelerin hesaplanmasının çok pahalı olduğunu söylemişti. - Riccardo Petraglia