Znajdź punkt, którego suma odległości do zestawu innych punktów jest minimalna

Question

Mam jeden zestaw (X) punktów (niezbyt duży, powiedzmy 1-20 punktów) i drugi (Y), znacznie większy zestaw punktów. Muszę wybrać jakiś punkt z Y, którego suma odległości do wszystkich punktów od X jest minimalna.

Wpadłem na pomysł, że potraktuję X jako wierzchołki wieloboku i znajdę środek ciężkości tego wielokąta, a następnie wybiorę punkt Y najbliższy środka ciężkości. Ale nie jestem pewien, czy środek ciężkości minimalizuje sumę jego odległości do wierzchołków wielokąta, więc nie jestem pewien, czy to dobry sposób? Czy istnieje algorytm rozwiązania tego problemu?

Punkty są określane przez współrzędne geograficzne.

Answer 1

Środek wieloboku może nie mieć racji, ale taki punkt istnieje.

W artykule: n-ellipses and the minimum distance problem, okazuje się, że jeśli punkty (zwane ogniska, twój zestaw X) nie są współliniowe wtedy

• Jest to unikalny punkt (zwany w środku), dla której suma odległości są minimalizowane. Punkt ten jest taki, że suma wektorów jednostkowych od tego punktu do ognisk wynosi zero!

• Zbiór punktów, dla których suma odległości jest stała jest wypukłą krzywą (zwany N-elipsa), zawierający Centre

• N-elipsy dla odległości D całkowicie zawiera n-elipsy dla każda inna odległość D „D”, dla których < D.

w ten sposób można zrobić jakiś rodzaj algorytmu wspinaczki wzgórze, aby znaleźć centrum.

Oczywiście te n-elipsy niekoniecznie są okręgami, więc samo wybieranie punktu najbliższego centrum może nie działać, ale może być dobrym przybliżeniem.

Możliwe, że możesz wykonać kilka preprocesorów na 20 punktach (jeśli są one ustalone), aby znaleźć dobry schemat partycjonowania (w oparciu o powyższe informacje).

Nadzieję, że pomaga.

Answer 2

Jeśli chcesz zminimalizować sumę kwadratów odległości (nie suma odległości), to punkt, który minimalizuje tej kwoty stanowi średnią punktów w X.

Dowód:

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...) 

suma jest zminimalizowane, gdy pochodna jest równa zero, który pojawia się, gdy Nx = x0+x1+..., więc x = (x0+x1+...)/N

pochodna jest symetryczny wokół tego punktu, a funkcja jest kwadratowa, więc jestem całkiem pewny, że najbliższa poin t w Y do tego średniego punktu jest najlepszy.

Minimalizacja odległości jest trudniejsza, ale podejrzewam, że ten sam algorytm, z większą swobodą w zbiorze Ys, który testujesz, również zadziała.

Answer 3

Ponieważ chcemy minimalnej sumy odległości, uważam, że można zredukować zbiór punktów X do jego średniej przestrzennej. Następnie możesz użyć drzewa KDTree lub jakiegoś drzewa partycjonowania przestrzennego, aby znaleźć punkt w Y najbliższy średniej przestrzennej X. Używanie drzewa partycjonowania przestrzennego może zaoszczędzić sporo pracy w porównaniu do sprawdzenia wszystkich możliwych punktów.

Answer 4

Przepraszam za sugerowanie brutalnej siły. Sposób, w jaki postawione jest pytanie, nie wiemy, gdzie leżą X, Y. Załóżmy, że X ma 30 punktów, Y to 1000 punktów. Następnie dla każdego punktu Y suma 30 odległości. Łącznie 30000 obliczeń, wykonane w migiem. Gwarantuje to minimum. Znalezienie "centrum" X i wybranie najbliższego Y będzie jedynie przybliżonym rozwiązaniem.

Bardziej interesujące jest znalezienie takiego punktu dla samego X. ignoruj ​​Y. Dla X tylko trzech punktów, punkt Fermat-Torichelli rozwiązuje problem.