imitatio creatio

( Próba rozwiązania problemu który podsunął depesz )

Mamy dany na wejściu zbiór A punktów (powiedzmy że 2D), należy jak najefektywniej znaleźć parę punktów najbardziej odległą od siebie.

1. Znajdujemy maksymalny wypukły podzbiór C zbioru A. Można spróbować powszechnie znanych algorytmów (tu, tu i tu). Jest nawet prezentacja (applet w Javie).

   Można też wykorzystać gotową bibliotekę napisaną w C.
   apt-get install libqhull5 libqhull-dev qhull-bin

2. C będzie istotnie mniejszy od A. W przybliżeniu:
   

   |C| = O(log |A|)

   (po polsku: liczba elementów C będzie proporcjonalna do logarytmu naturalnego z liczby elementów A)

   Można to empirycznie sprawdzić następującym testem (rbox generuje zbiór losowych punktów, a qhull liczy dla nich maksymalny podzbiór wypukły):

   
for n in `seq 10 10 100 ; seq 5000 5000 100000`; do
vertices=`rbox $n D2 n z | qhull p | wc -l`
vertices=$[ vertices - 2 ]
logn=`echo “scale=2; l( $n ) ” | bc -ql`
wsp=`echo “scale=2; $vertices / $logn ” | bc -q`
echo -e “n=$n \t vertices=$vertices \t logn=$logn \t (vertices/logn)=$wsp”
done


3. Dla znalezionego zbioru C stosujemy prosty algorytm do znalezienia najdłuższej odległości. Prosty czyli taki “każdy z każdym”, który działa w O( n² ).
4. W sumie uzyskamy program działający w O( log²|A| ).
   Nie liczę czasu spędzonego na wyliczaniu C. Wg autorów qhull jest to O( |A| log |C| ).

Pozostaje jeszcze zakodowanie tego w SQL… ale to chyba tylko takie zboczenie bazodanowca :)