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:
- The step where subproblems are combined takes place in one lower dimension.
- The subproblems in the combine step satisfy a sparsity condition.
- Sparsity Condition: Any cube with side length 2δ contains O(1) points of S.
- 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.