Dato un insieme di punti in 2d spazio P, dove Pi = (Xi, Yi),trovare un punto tale che la distanza massima a qualsiasi punto in un insieme di punti P viene minimizzata
devo trovare un punto di mira T tale che la distanza massima da qualsiasi Pi sia minimizzata.
T non ha bisogno di esistere in P, e può essere definito arbitrariamente
Esiste un algoritmo che posso usare per questo?
Questo è il smallest circle problem.
sì, questo è fondamentalmente quello che voglio, tranne che non ho bisogno del raggio ho solo bisogno del punto centrale. – jdeuce
L'articolo di Wikipedia contiene un algoritmo di tempo lineare per risolvere questo problema. Dubito fortemente che non richiedere un raggio nell'output consentirà soluzioni più veloci. –
sì, la carta è difficile da leggere, hai qualche pseudocodice per l'alg? – jdeuce
http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
che questo potrebbe essere una soluzione al tuo problema con abbastanza buona spiegazione, ma è O (n^2)
Il problema è che il collegamento all'algoritmo attuale è rotto. Ma un bel grafico dal vivo per rappresentare l'algoritmo. – Paparazzi
non l'ho provato, ma penso che la soluzione giusta è:
(min (Xi) + max (Xi))/2, (min (Yi) + max (Yi))/2)
in realtà questa è un'approssimazione. Immagina un quadrato attorno al cerchio più piccolo, la quantità massima che l'approssimazione può essere fuori, è la distanza dall'angolo del quadrato al cerchio. – jdeuce
Qualsiasi o somma non sarà lo stesso punto. – Paparazzi
Perché non è ottimale? –
Ho aggiornato la domanda per eliminare il riferimento alla soluzione approssimativa che stavo usando, poiché è irrilevante per la discussione. – jdeuce