Java Reference
In-Depth Information
13.11 Select any two of the point representations described in this chapter (i.e., the
k-d tree, the PR quadtree, the bintree, and the point quadtree). Implement
your two choices and compare them over a wide range of data sets. Describe
which is easier to implement, which appears to be more space efficient, and
which appears to be more time efficient.
13.12 Implement a representation for a collection of (two dimensional) rectangles
using a quadtree based on regular decomposition. Assume that the space
being represented is a square whose width and height are some power of
two. Rectangles are assumed to have integer coordinates and integer width
and height. Pick some value c, and use as a decomposition rule that a region
is subdivided into four equal-sized regions whenever it contains more that c
rectangles. A special case occurs if all of these rectangles intersect at some
point within the current region (because decomposing such a node would
never reach termination). In this situation, the node simply stores pointers
to more than c rectangles. Try your representation on data sets of rectangles
with varying values of c.
