trova un punto più vicino ad altri punti

Question

Dato N punti (in 2D) con coordinate xey. Devi trovare un punto P (in N punti dati) tale che la somma delle distanze da altri (N-1) punti a P sia minima.

per es. N punti dati p1 (x1, y1), p2 (x2, y2) ...... pN (xN, yN). abbiamo trovato un punto P tra p1, p2 .... PN la cui somma di distanze da tutti gli altri punti è minima.

Ho usato un approccio a forza bruta, ma ho bisogno di un approccio migliore. Ho anche provato a trovare la mediana, la media ecc. Ma non funziona per tutti i casi.

quindi mi è venuta l'idea che avrei trattato X come un vertice di un poligono e trovato il centroide di questo poligono, e quindi sceglierò un punto da Y più vicino al centroide. Ma non sono sicuro che il centroide minimizzi la somma delle sue distanze rispetto ai vertici del poligono, quindi non sono sicuro che sia un buon modo? C'è qualche algoritmo per risolvere questo problema?

Answer 1

Se i tuoi punti sono ben distribuiti e se ce ne sono così tanti che la forza bruta (calcolando la distanza totale da ciascun punto ad ogni altro punto) non è attraente, il seguente potrebbe darti una risposta abbastanza buona. Per "ben distribuito" intendo (approssimativamente) uniformemente o (approssimativamente) a caso e senza marcato raggruppamento in più posizioni.

Creare una griglia uniforme k*k, dove k è un numero dispari, in tutto lo spazio. Se i tuoi punti sono distribuiti correttamente, quello che stai cercando è (probabilmente) nella cella centrale di questa griglia. Poiché tutte le altre celle della griglia contano il numero di punti in ogni cella e approssimano la posizione media dei punti in ogni cella (utilizzare il centro della cella o calcolare la media (x,y) per i punti nella cella).

Per ciascun punto nella cella centrale, calcolare la distanza da ogni altro punto nella cella centrale e la distanza media ponderata rispetto ai punti nelle altre celle. Questa sarà, naturalmente, la distanza dal punto alla posizione "media" dei punti nelle altre celle, ponderata dal numero di punti nelle altre celle.

Dovrai destreggiarti con la maggiore precisione dei valori più alti per k contro il maggiore carico di calcolo e capire cosa funziona meglio per i tuoi punti. Se la distribuzione dei punti tra le celle è tutt'altro che uniforme, questo approccio potrebbe non essere adatto.

Questo tipo di approccio è ampiamente utilizzato nelle simulazioni su larga scala in cui i punti hanno proprietà, come la gravità e la carica, che operano su distanze. Che si adatti alle tue esigenze, non lo so.

Answer 2

Non sono sicuro di aver compreso la tua domanda ma quando si calcola l'albero di copertura minimo la somma da qualsiasi punto a qualsiasi altro punto dall'albero è minima.

Answer 3

Il punto in esame è conosciuta come la geometrica mediana

Il baricentro o il centro di massa, definita analogamente alla mediana geometrica minimizzando la somma dei quadrati delle distanze di ciascun campione, è disponibile da un formula semplice - le sue coordinate sono le medie delle coordinate dei campioni ma nessuna formula è nota per la mediana geometrica, ed è stato dimostrato che nessuna formula esplicita, né un algoritmo esatto che coinvolge solo operazioni aritmetiche e radici kth può esistere in generale .