Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

binary space partitions

0 views
Skip to first unread message

Fred Thiele

unread,
Jul 9, 2002, 9:39:04 AM7/9/02
to
Hallo NG,

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


0 new messages