Weekly Note 13, DM45, spring 2007
Discussion Section May 9
-
Exercises 14.5, 14.12, 14.13, 14.14.
-
In the balancing algorithm for quadtrees, which runs in O(dn),
where n is the size of the tree,
the O(d)-part is due to searches for neighbor nodes
to check if they are more finely divided than the current node.
Here, d denotes the height of the quadtree.
Consider maintaining a constant amount of extra information
in the internal nodes of a quadtree such that this information
can be obtained in constant time, thereby reducing the time
complexity of the balancing algorithm to O(n).
Announcements
-
Note that we are not meeting on May 7
and that the regular lecture slot on May 9
is used for exercises instead.
Last modified: Thu May 3 10:08:47 CEST 2007
Kim Skak Larsen
(kslarsen@imada.sdu.dk)