Come generalizzare il caso planare del problema della coppia più vicina a d dimensioni?

4

Sto provando a creare una soluzione per il problema Coppia più vicina che utilizza i punti bidimensionali. Ho fatto una ricerca approfondita su google, ma sembra che non vi sia alcuna spiegazione per il caso d-dimensionale a parte ciò che è su wikipedia:

the divide-and-conquer algorithm can be generalized to take O(n log n) time for any constant value of d.

e questo documento che ho trovato affermando:

  • Two key features of the divide and conquer strategy are these:
    1. The step where subproblems are combined takes place in one lower dimension.
    2. The subproblems in the combine step satisfy a sparsity condition.
    3. Sparsity Condition: Any cube with side length 2δ contains O(1) points of S.
    4. Note that the original problem does not necessarily have this condition.

...

  • Given n points with δ-sparsity condition, find all pairs within distance ≤ δ.
  • Divide the set into S1, S2 by a median place H. Recursively solve the problem in two halves.
  • Project all points lying within δ thick slab around H onto H. Call this set S'
  • Recursively solve the problem for S' in d − 1 space.

ma non riesco a comprendere le indicazioni fornite nei documenti sopra. Qualcuno può descrivere in parole povere come faccio a generalizzare la soluzione 2d alle dimensioni d? È addirittura necessario o la soluzione 2d funzionerà?

Capire il caso 2d non è stato così difficile, ma sembra che ci sia poco conosciuto riguardo alla versione d-dimensionale e io non sono un matematico.

    
posta Adam Arold 29.12.2015 - 08:27
fonte

1 risposta

3

Generalizzare l'algoritmo divide et impera da Wikipedia al caso dimensionale è semplice:

Ecco la descrizione dell'algoritmo adottato (modifiche in grassetto):

  1. Ordina i punti in base alle loro coordinate x.

  2. Dividi il set di punti in due sottoinsiemi di uguale dimensione con un (d-1) piano verticale iperdimensionale definito da x = xmid.

  3. Risolvi il problema in modo ricorsivo nella metà "sinistra" e "destra" dello spazio di coordinate, definito da x < = xmid e x > = xmid . Questo produce rispettivamente le distanze minime sinistra e destra dLmin e dRmin.

  4. Trova la distanza minima dLRmin tra l'insieme di coppie di punti in cui un punto si trova sulla "sinistra" del piano di divisione e il secondo punto si trova sulla "destra" ".

  5. La risposta finale è il minimo tra dLmin, dRmin e dLRmin.

Si noti che il passaggio 4 può essere eseguito in tempo lineare per 2 dimensioni, ma richiede i passi O (n * log (n) ^ (d-1)) per le dimensioni d. Maggiori dettagli sono descritti qui , che include il caso d > 2.

Si noti inoltre che per i dati del mondo reale può essere una buona idea passare da un asse di coordinate all'altro da un passaggio ricorsivo a quello successivo (ma che si applica già al caso planare).

    
risposta data 29.12.2015 - 09:33
fonte

Leggi altre domande sui tag