distanta maxima intre 2 puncte in spatiu

[•MarcvsHdr]

Descrierea problemei e simpla: N puncte in spatiu, se cere cea mai mare distanta euclidiana/Manhattan dintre ele. Nu va faceti probleme pentru memorie sau neaparat timp. Ma intereseaza algoritmi cat mai rapizi, si, pe cat posibil, nu chiar SF. Sau, ma rog, orice e bun.
Versiunea in plan se poate rezolva cu "rotating calipers" in O(n), odata ce ai determinat infasuratoarea convexa a punctelor, cel putin asta pentru distante euclidiene. Pentru distante Manhattan, nu stiu un algoritm, dar presupun ca e asemanator ca si pentru 3 dimensiuni.
     Oricum, am mai vazut problema asta, versiunea Manhattan, pe undeva (daca nu ma insel, poate chiar .campion sau Moisil, dar nu bag mana in foc), si am o sursa-solutie oficiala, dar nu inteleg algoritmul din spatele ei. Mai ales ca face si tot felul de operatii de biti, care daca nu stii exact ce rol au, cam greu sa te prinzi singur.
    Deci... stie cineva cum se face?

[•azotlichid]

Pentru distanta Manhattan, ideea este foarte diferita de cea pentru distanta euclidiana.

Considera planul 2D si punctele de coordonate xi, yi.
Distanta Manhattan intre doua puncte x1, y1 si x2, y2 este
|x1 - x2| + |y1 - y2|

Expliciteaza modulul si gaseste o rezolvare in 2^D, pentru D = numarul de dimensiuni.  

[cristi8]

problema cu distanta manhattan a fost pe .campion, si din cate stiu era explicat algoritmul la "Descriere solutie"

[•MarcvsHdr]

Considera planul 2D si punctele de coordonate xi, yi.
Distanta Manhattan intre doua puncte x1, y1 si x2, y2 este
|x1 - x2| + |y1 - y2|
Expliciteaza modulul si gaseste o rezolvare in 2^D, pentru D = numarul de dimensiuni.  

Mda. Stiu si eu formula pentru distanta Manhattan intre 2 puncte. Si e aberant ca algoritmul sa fie 2^D, unde D={2,3} in majoritatea cazurilor. Daca iei la rand fiecare 2 puncte, pentru 1000 sau mai mult de puncte ce faci? Ca altfel nu inteleg ce vre isa zici.

[•azotlichid]

fie...mai exact e O(N*D + 2^D), unde D e numarul de dimensiuni iar N e numarul de puncte. gandeste un pic inainte

[•Cosmin]

Cica mai exact , corect eventual.