Úlohou je nájsť najmenší štvorec, ktorý pokryje všetky body alebo jeden vynechá.

Bruteforce

Najpriamočiarejšie riešenie je vyskúšať postupne zahodiť každý jeden bod. Keďže bodov je $n$, máme $n$ možností, ktorý bod vynechať. Pre každú z týchto možností prejdeme všetkých zvyšných $n - 1$ bodov a nájdeme medzi nimi najväčšiu aj najmenšiu súradnicu $x$ ($x_{max}$, $x_{min}$), najväčšiu aj najmenšiu súradnicu $y$ ($y_{max}$, $y_{min}$). Pomocou nich vypočítame potrebnú stranu štvorca tak, že vezmeme rozdiely $x_{max} - x_{min}$ a $y_{max} - y_{min}$ a vyberieme z nich ten väčší. Nakoniec len zistíme, ktorá voľba zahodeného bodu nám dala najmenší výsledok.

Problémom je ale časová zložitosť tohto riešenia. Keďže pre každý z $n$ bodov prechádzame znova celé pole s dĺžkou $n$, dáva nám to celkovú časovú zložitosť $O(n^2)$.

Zaujímavá myšlienka

Ktoré body reálne určujú veľkosť ohraničujúceho štvorca? Sú to len tie body, ktoré ležia pri okraji. Zjavne nemá zmysel hľadať vždy nanovo najmenší štvorec pre body, ktoré ležia uprostred, kedže krajné body sa nezmenia. Stačilo by teda nájsť tieto štyri extrémy ($x_{max}$, $x_{min}$, $y_{max}$, $y_{min}$) a skúsiť odstrániť body, ktoré majú aspoň jednu z týchto súradníc.

Aby sme si to ešte viac zjednodušili a nemuseli pre každý z tých štyroch bodov prechádzať všetky body a hľadať nové maximá a minimá, môžeme si pre každý extrém pamätať dve hodnoty: najextrémnejšiu a druhú najextrémnejšiu hodnotu v poradí. Takto vieme, že ak odstránime bod s hodnotou $x_{max}$, tak nové $x_{max}$ sa stane druhá najväčšia hodnota.

Optimálne riešenie

Prvým prechodom cez všetky body si zapamätáme dve najextrémnejšie hodnoty pre každú stranu ($x_{max}$, $x_{min}$, $y_{max}$, $y_{min}$). Toto sa dá aj jedným prechodom, teda v lineárnom čase.

Prečo je potrebné prejsť všetky body ešte raz? Naivný prístup predpokladá, že extrémy patria štyrom rôznym bodom. V reálnom svete však jeden jediný bod môže byť extrémom na viacerých osiach naraz (napríklad bod v rohu môže byť súčasne najviac vľavo ($x_{min}$​) aj najnižšie ($y_{min}$​)). Ak by sme tento bod vymazali, zmení sa naraz šírka aj výška celého ohraničenia. Ak by sme body neprešli znova, nevedeli by sme, ktoré extrémy patria k sebe, a mohli by sme kombinovať neexistujúce súradnice.

Prejdeme teda všetky body druhýkrát. Ak je to bod, ktorý je extrémom (skontrolujeme to pre obe súradnice), pozrieme sa na druhú najextrémnejšiu hodnotu v poradí pre danú os. Vypočítame novú stranu štvorca a priebežne si ukladáme minimum.

Celková časová zložitosť je $O(n)$, keďže $n$ bodov prejdeme dvakrát. Pamäťová zložitosť je v tomto prípade $O(n)$, lebo si pamätáme všetkých $n$ bodov, aby sme ich vedeli prejsť druhý krát.