Vielleicht kann mir jemand von euch bei dem Beweis des folgenden Satzes
helfen. Es geht um Größe und Zeitaufwand bei bei dem Algorithmus des
randomisierten BSP-Baums.
Satz: Angenommen die Segmente in N durchschneiden sich nicht, dann ist die
erwartete Größe des BSP(N), die durch den Algorithmus erzeugt wird O(n log
n) und der erwartete Zeitaufwand des BSP(N) ist O(n² log n).
bye
--
Fred Thiele
fr...@gmx.fr