Distanza tra coppie di punti su un piano cartesiano

Mi è stata recentemente posta la seguente domanda, in un'intervista a Foursquare. Non ero in grado di codificare questo.Distanza tra coppie di punti su un piano cartesiano

Vengono indicati N punti (xi, yi) dove 1 < = i < = N e due numeri aeb, in modo tale che la distanza tra due punti (x1, y1) e (x2, y2) sia massima (a * | x1-x2 |, b * | y1-y2 |), come possiamo calcolare la somma delle distanze tra ogni coppia di punti?

Il numero di punti N è un numero elevato.

Qualcuno può aiutare con come risolvere questa domanda? Per favore spiega l'algoritmo, oltre alla forza bruta, del traversare su tutte le coppie di punti.

fonte

2015-04-19 user12457112

Non sono sicuro di capire come non si possa ottenere questo risultato. Non puoi semplicemente scorrere tutte le coppie di punti, calcolare l'istruzione 'max (...)' e sommare tutte le chiamate 'max (...)'? – rayryeng

Questa è la forza bruta. Cerco un algoritmo migliore. Ovviamente potrei pensarci. – user12457112

Ti hanno chiesto un algoritmo di forza bruta o qualsiasi algoritmo? La forza bruta è meglio che non dare nulla. – rayryeng

Iniziare ridimensionando l'asse, per eliminare i fattori a e b. Definire x' = a * x, y' = b * y'. Allora la distanza è:

max(a*|x1-x2|,b*|y1-y2|) = 
max(|a*x1-a*x2|,|b*y1-b*y2|) = 
max(|x'1-x'2|,|y'1-y'2|)

secondo luogo, ruotare il sistema di coordinate di 45 gradi, per cambiarlo Taxicab geometry. Definire s = (x' + y')/2, t = (x' - y')/2. Quindi abbiamo x' = s + t, y' = s - t.

Quindi possiamo riscrivere definizione della distanza ancora:

max(|x'1-x'2|,|y'1-y'2|) = 
max(|s1 + t1 - s2 - t2|,|s1 - t1 - s2 + t2|) = 
max(|(s1 - s2) + (t1 - t2)|,|(s1 - s2) - (t1 - t2)|) = 
|s1 - s2| + |t1 - t2| 
-- last equation comes from the fact that max(|a + b|, |a - b|) = |a| + |b|

Con questa definizione possiamo riassumere separatamente distanze lungo s asse e separatamente lungo t asse e sommare i risultati.

La risoluzione della versione unidimensionale di questo problema è piuttosto semplice. Si ordinano i punti lungo l'asse. Quindi ogni segmento compreso tra 0 (basato su 0) i -esimo e i+1 -th punto contribuirà a (i + 1) * (N - i - 1) * distance. È sufficiente sommare questi valori.

La soluzione complessiva richiede O(n lg n), poiché è necessario ordinare i punti due volte.

fonte

2015-04-19 20:45:43 zch

Non capisco la tua soluzione per il problema 1D Prendi i: [0..n-1] o [1..n]? Non ci arrivo neanche con: Prendi 3 punti (1,0), (2,0), (3,0), A = 1, B = 0: la distanza totale dovrebbe essere 4. secondo la formula: '1 * (3-1-1) * 1 + 2 * (3-2-1) * 1 = 1' per i = [1..3] o '0 * (3-0-1) * 1 + 1 * (3-1-1) * 1 = 1' per i = [0..2]. – Wouter

Ottima soluzione, potenziato !! Ma proverò a imparare qualcosa qui.La chiave è stata la sostituzione di s e t qui.Come sei arrivato con la sostituzione s = (x + y)/2 e t = (xy)/2? Domande sulla geometria comune?
E anche in che modo è correlata alla geometria del taxi e rotazione dell'asse di 45 gradi, perché allora il nuovo punto sarebbe stato qualcos'altro? (Applicare la formula s = xcosQ - ysinQ, t = xsinQ + ycosQ) –

@Wouter, corretta la formula, ero fuori da uno. Ci sono i punti 'i + 1' sulla sinistra del segmento ei punti' N - i - 1' sulla destra, quindi ci saranno '(i + 1) * (N - i - 1)' coppie di punti che contenere questo segmento. – zch

di voler calcolare

sum_i sum_j max(a |xi - xj|, b |yi - yj|).

semplificare il problema attraverso la mappatura xi' = a xi e yi' = b yi e informatica

sum_i sum_j max(|xi' - xj'|, |yi' - yj'|).

semplificare il problema attraverso la mappatura ui = (xi + yi)/2 e vi = (xi - yi)/2 e informatica

sum_i sum_j (|ui - uj| + |vi - vj|) 
    = sum_i sum_j |ui - uj| + sum_i sum_j |vi - vj|.

Per risolvere il primo sottoproblema nel tempo O (n log n), ecco alcuni Python.

def one_d(us): 
    us = sorted(us) 
    return sum((2 * i - (len(us) - 1)) * u for (i, u) in enumerate(us))

fonte

2015-04-19 20:49:01

Distanza tra coppie di punti su un piano cartesiano

risposta

Problemi correlati