Średnica zbioru
( 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.
- 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 - 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
- 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( n2 ).
- W sumie uzyskamy program działający w O( log2|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 :)
