(20 points)
Assume we have N points P in the plane organized in a quad tree.
Assume the root of the tree represents the quadrant [0,1]x[0,1].
The nodes of the quad tree have the fields
leaf: boolean, data.x, data.y,
origin.x, origin.y, size: real, Q[0..3]: array of pointers to nodes.
In this problem assume that reals are fully represented and there
are no floating point errors.
Design a function "intersect" which takes arguments a,b,d,x,y,r and
retruns true if the square with left-bottom corner (a,b) and side d
intersects the circle with center (x,y) and radius r. The square
and circle include their boundaries and interior.
Use the insersect function above to design a procedure which
given a point (x,y) (not necessarily in P)
and radius r prints out all the points in P within distance r
of (x,y). Your procedure should only visit quadrants where there
is some possiblity that there is a point in P within distance r of
(x,y).
Suppose that the minimum distance between any two points in P is
m. As a function of N, m and r give a good upper bound on the number of
points output by your procedure. As a function of m, what is an upper bound on
the height of the quad tree? What is the overall time
complexity of your procedure as a function of the number of points
output and m.
(10 points)
Consider B-trees of order 3 which is also known as a 2-3 tree.
In this case each internal node has
2 or 3 children and each leaf has either one or two keys.
Show the result of inserting 1,2,3,4,5,6,7,8,9,10,11,12 into an
initially empty 2-3 tree. Show the tree after each insertion.