Come trovare due punti più distanti?

Question

Questa è una domanda che mi è stata chiesta per un colloquio di lavoro qualche tempo fa. E ancora non riesco a capire una risposta sensata.

domanda è:

si è dato insieme di punti (x, y). Trova 2 punti più lontani. Distanti l'uno dall'altro.

Ad esempio, per i punti: (0,0), (1,1), (-8, 5) - i più distanti sono: (1,1) e (-8,5) perché la distanza tra loro sono più grandi da entrambi (0,0) - (1,1) e (0,0) - (- 8,5).

L'approccio ovvio è calcolare tutte le distanze tra tutti i punti e trovare il massimo. Il problema è che è O (n^2), che lo rende proibitivo per i dataset di grandi dimensioni.

C'è un approccio con i primi punti di tracciamento che si trovano sul confine e quindi calcola le distanze per loro, sulla premessa che ci saranno meno punti sul confine che "dentro", ma è ancora costoso, e fallirà nel peggiore caso.

Ho provato a cercare sul Web, ma non ho trovato alcuna risposta ragionevole - anche se questo potrebbe essere semplicemente la mia mancanza di capacità di ricerca.

Answer 1

EDIT: Un modo è quello di trovare il convesso scafo http://en.wikipedia.org/wiki/Convex_hull della serie di punti e poi i due punti distanti sono i vertici di questo.

Possibilmente risposta qui: Algorithm to find two points furthest away from each other

anche:

• http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

Answer 2

Algoritmi per punto limite abbondano (cercare algoritmi di scafo convesso). Da lì, dovrebbe occorrere O (N) per trovare i punti opposti più lontani.

Dal commento dell'autore: per prima cosa trova una qualsiasi coppia di punti opposti sullo scafo, quindi giragli intorno in modo semi-serrato. A seconda degli angoli tra i bordi, dovrai far avanzare uno dei due camminatori o l'altro, ma sarà sempre necessario O (N) per circumnavigare lo scafo.

Answer 3

A pochi pensieri:

Si potrebbe guardare solo i punti che definiscono il convesso del vostro insieme di punti per ridurre il numero, ... ma sembra ancora un po ' "non ottimale".

Altrimenti potrebbe esserci un approccio ricorsivo quad/oct-tree per il rapido collegamento di alcune distanze tra insiemi di punti ed eliminare ampie parti dei dati.

Answer 4

Un punto di partenza potrebbe essere guardando i problemi al più vicino punti, che sono state esaminate.Wikipedia elenca alcune opzioni:

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

Answer 5

Un algoritmo stocastico di trovare la coppia più lontana sarebbe

• scegliere un punto casuale
• Prendi il punto più lontano ad esso
• Ripetere una Poche volte
• Rimuovi tutti i punti visitati
• Scegli un altro r punto casuale e ripetere alcune volte.

Sei in O (n) fino a quando si predeterminerà "alcune volte", ma non è garantito che trovi effettivamente la coppia più distante. Ma a seconda della serie di punti, il risultato dovrebbe essere abbastanza buono. =)

Answer 6

Questa domanda è stata introdotta in Introduzione all'algoritmo. Ha menzionato 1) Calcola Convex Hull O (NlgN). 2) Se è presente M vectex su Convex Hull. Quindi abbiamo bisogno di O (M) per trovare la coppia più lontana.

Trovo questo link utile. Comprende l'analisi dei dettagli dell'algoritmo e del programma. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Desideri questo sarà utile.

Answer 7

Si sta cercando un algoritmo per calcolare il diametro di un set di punti, Diam (S). Si può dimostrare che questo è uguale al diametro dello scafo convesso di S, Diam (S) = Diam (CH (S)). Quindi prima calcola lo scafo convesso del set.

Ora devi trovare tutti i punti degli antipodi sullo scafo convesso e raccogliere la coppia con la massima distanza. Ci sono O (n) punti antipodali su un poligono convesso. Quindi questo dà un algoritmo O (n lg n) per trovare i punti più lontani.

Questa tecnica è nota come Calibri rotanti. Questo è ciò che Marcelo Cantos descrive nella sua risposta.

Se si scrive attentamente l'algoritmo, è possibile fare a meno degli angoli di calcolo. Per i dettagli, controllare questo URL.

Answer 8

Sembra facile se i punti sono indicati in coordinate cartesiane. Così facile che sono abbastanza sicuro di trascurare qualcosa. Sentiti libero di indicare cosa mi manca!

1. Trova i punti con i valori massimo e minimo delle loro coordinate x, yez (6 punti in totale). Questi dovrebbero essere i più "remoti" di tutti i punti di confine.
2. Calcolare tutte le distanze (30 Distanze unici)
3. trovare la distanza massima
4. I due punti che corrispondono a questa distanza max sono quelli che stai cercando.

Answer 9

Dato un insieme di punti {(x1, y1), (x2, y2) ... (xn, yn)} trova 2 punti più distanti.

Il mio approccio:

1). Hai bisogno di un punto di riferimento (xa, ya), e sarà:
xa = (x1 + x2 + ... + xn)/n
ya = (y1 + y2 + ... + yn)/n

2). Calcola tutta la distanza dal punto (xa, ya) a (x1, y1), (x2, y2), ... (xn, yn)
Il primo "punto più distante" (xb, yb) è quello con il massima distanza

3). Calcola tutta la distanza dal punto (xb, yb) a (x1, y1), (x2, y2), ... (xn, yn)
L'altro "punto più distante" (xc, yc) è quello con il massima distanza

Così avete ottenuto il vostro punti più distanti (XB, YB) (XC, YC) a O (n)

Ad esempio, per i punti: (0,0), (1,1), (- 8, 5)

1). Punto di riferimento (xa, ya) = (-2.333, 2)

2). Calcolare le distanze:
da (-2.333, 2) a (0,0): 3.073
da (-2.333, 2) a (1,1): 3.480
da (-2.333, 2) a (-8 , 5): 6.411
Quindi il primo punto più distante è (-8, 5)

3). Calcolare le distanze:
da (-8, 5) a (0,0): 9.434
da (-8, 5) a (1,1): 9.849
da (-8, 5) a (-8 , 5): 0
Così l'altro punto più lontano è (1, 1)

Answer 10

un'occhiata a triangoli ad angolo retto A- (x1, y1), B- (x2, y2) e la distanza b/w A e B è = sqrt [(| x1 | + | x2 |)^2 + (| y1 | + | y2 |)^2]

Answer 11

Trova la media di tutti i punti, misura la differenza tra tutti i punti e la media, prendi il punto più lontano dalla media e trova il punto più lontano da esso. Questi punti saranno gli angoli assoluti dello scafo convesso e i due punti più distanti. Recentemente ho fatto questo per un progetto che necessitava di scafi convessi limitati a piani infiniti diretti casualmente. Ha funzionato alla grande.