Newsgroup: it.scienza.informatica
Titolo: applicazioni della closest pair approssimata

Il closest pair problem, per chi non lo sapesse, č definito cosě:
dato un insieme di n punti, trovare la coppia di punti piů vicini tra loro.
Sto cercando delle applicazioni pratiche in cui č possibile applicare il 
closest pair problem approssimato: applicazioni in cui non č indispensabile 
trovare la coppia piů vicina (mi accontento di una coppia molto vicina) 
purché la ricerca sia molto veloce.
Sapete aiutarmi?
Grazie, antonio 

Giusto una idea molto informale:
ad ogni punto assegni il suo valore di posizione nello spazio
n-vettoriale che consideri, poi fai un bel quicksort della lista di
valori ottenuti, usando una relazione opportuna, ottienendo una lista
ordinata di posizioni, scorri la lista calcolando le distanze tra il
punto n e quello n+1, e prendi la coppia di punti (n,n+1) con distanza
minore.

 Grazie, antonio
...a meno che mi sfugga qualcosa, non mi sembra un problema troppo
complicato e non vedo quale problematica possa essere interessata ad una
simile 'funzione' se non nell'ambito delle operations research (teoria dei
grafi).
Se 'ci si accontenta' di due punti 'abbastanza vicini' allora bisognerebbe
necessariamente definire un 'intervallo di vicinanza' col quale confrontare
i risultati della funzione.
John.


In realtà questo quesito ha applicazioni nei più svariati campi: information 
retrieval, data minig, biologia computazionale, analisi statistica, computer 
vision, analisi geografica, pattern recognition, protocolli distribuiti, 
ecc.
Il fatto è che, per quanto ne so, queste applicazioni pratiche utilizzano la 
soluzione esatta. Mentre io ho bisogno di applicazioni della soluzione 
approssimata...booo.... 

 ha scritto nel messaggio 
news:60m2a21img31bimeg...@4ax.com...

1)
Il discorso che fai tu va bene quando i punti sono posti su una retta: 
ordino e calcolo da distanza di ogni punto dal successivo.
Già nel piano non è più possibile fare questo discorso: due punti le cui 
coordinate x siano molto vicine non è detto che siano vicini (ad es A=[3,3], 
B=[3.01, 100]).
Stesso discorso puoi applicarlo alle coordinate y.
Cosa intendi per "...usando una relazione opportuna..."?
2)
Il mio problema non è cmq la soluzione al problema (ne conosco già 
parecchie), ma le applicazioni pratiche al problema approssimato.
A presto,
Antonio 

 approssimata...booo....
Continuo a non capire.
Sia A un insieme di punti a(i) nello spazio,
Sia D un insieme contenente i segmenti d(j), cioè tutte le distanze
possibili tra tutti i punti a(i)
 
Sarà possibile ordinare l'insieme D in modo che sia sempre 
         d(j-1) < d(j) < d(j+1)  
a questo punto si hanno tutte le soluzioni possibili ordinate e basta
scegliere un intervallo I tale che  
        d(j) < I 
e si ha già una soluzione esatta al tuo problema, laddove una
soluzione 'approssimata' potrebbe essere  d(j+1).
Oppure mi sfugge qualcosa o non ho capito il problema  ???
John. 

applicazioni pratiche al problema approssimato.
Data una societa' che deve ridurre il personale, trovare le coppie di
persone con compiti similari, dove eliminando una delle due i compiti
da svolgere rimangono il piu' possibile coperti.
-- 
Andrea Rimicci

 n-vettoriale che consideri
Cioè?
Qual'è il valore di posizione del punto (x,y)?
In pratica, dici di definire una funzione f: RxR --> R  ???
E com'è definita questa funzione? 

E com'č definita questa funzione? 
La definisci tu, in base alle tue esigenze, e in base al problema
reale che vuoi modellare. Da qui l'approssimazione.

 reale che vuoi modellare. Da qui l'approssimazione.
Ma terra terra, mi dai una f: RxR-->R che mi permetta
1) di assegnare ad ogni punto bidimensionale un valore
2) ordinando tutti i valori degli n punti in input e selezionando i due 
valori piů "vicini", ottengo la closest pair