Distanta Manhattan

[•nparfene2004]

Considerand ca se dau n puncte in plan de coordonate intregi, pentru calculul distantei Manhattan minime dintre doua puncte este vreun algoritm O(n log n) sau mai bun?

V-as ruga sa-mi dati si mie vreun articol pe tema aceasta, sau vreun link.
Va multumesc!

[•wefgef]

Problema, intr-o forma usor modificata, se gaseste si pe infoarena: http://infoarena.ro/problema/harta2.

Exista un algoritm O(N log N) cu hashuri care merge destul de incet, si altul cu aceeasi complexitate mult mai rapid si usor de implementat care adapteaza algoritmul pentru gasirea celor mai apropiate doua puncte din plan. Poti gasi in Cormen la capitolul de geometrie acest algoritm.