The Postal Owl

Máme $n$ bodů v rovině a chceme najít dvojici s nejmenší vzdáleností. To lze snadno v $O(n^2)$, cílem je tedy dostat lepší časovou složitost. (Předpokládejme, že změřit vzdálenost dvou bodů trvá $O(1)$.)

Nabízí se následující řešení založené na Rozděl a panuj:
1. rozdělíme body vodorovnou přímkou podle mediánu y-ových souřadnic na dvě poloviny (předpokládejme, že medián najdeme v lineárním čase --- to bude na přednášce),
2. rekurzivně spočítáme nejmenší vzdálenosti $\varepsilon_1$ a $\varepsilon_2$ v obou polovinách bodů,
3. spočítáme nejmenší vzdálenost dvou bodů ležících v různých polovinách, na což se stačí zaměřit na pás o šíři $2\min(\varepsilon_1, \varepsilon_2)$ podél dělící přímky.

Úkolem je domyslet detaily, tedy hlavně jak provést 3. krok, a analyzovat časovou a paměťovou složitost. (Můžete použít i jiné řešení, bude-li mít stejně dobrou nebo lepší složitost.)