QUESTION $3$

A $2-$D tree is a binary tree where every node stores a two$-$dimensional point.

Any node at odd level has an x$-$coordinate which is greater than or equal to the x$-$

coordinates of all nodes in its left subtree, and less than the x$-$coordinates of all nodes in its

right subtree. Similarly, any node at even Jevel has a y$-$coordinate which is greater than or

equal to the y$-$coordinates of all nodes in its left subtree, and less than the y$-$coordinates of

all nodes in its right subtree.

The following is an example $2-$D tree containing the points $(7,2),(5,4),(3,6),\{2,3),(4,7)$ and

$(8,1),$ shown as a binary tree and in an equivalent graphical representation. The latter

shows how every node of the tree recursively splits the two$-$dimensional space.

$10$y

$8$

X $$Level $1$ @

it G $\%|$

Yo kevel$2$z

$4$

X$$Level$3$

& B & $|$

$\%$ z $0$ & T $10$

A $2-$D tree is implemented by the class:

public class TwoDTree $\{$

private class Node $\{$

Point p; $//$ The point stored in this node.

Node left; Node right; $//$ The left and right child nodes.

int level; $//$ The level of the node; root is at level $1.$

$\}$

private Node root; $//$ Reference to the root of the tree

$-\}$

Here Point is the following class:

public class Point $\{$

public double x;

public double y;

Point $($int x$0,$ int y$0)\{$

x$=$x$0$;y$=$y$0$;

$\}$

$\}$

Give an efficient implementation of the following method of the TwoDTree class:

Point findKthClosest$($Point centre, double radius, int k$)$

The arguments of the method are centre and radius, defining a search circle, and a number

k $($k$>0).$ The method returns the k$-$th closest point to centre, out of those points which are

stored in the tree and are inside the search circle. If the tree contains fewer than k points

inside the search circle then the method returns null.

The implementation should minimise the required memory needed. It should also avoid

searching inside subtrees whose points are guaranteed to be outside the search circle.

Please comment on the time and space performance of your code.

Note that given a circle with centre $($x$.,$ yc$)$ and radius r:

o The squared distance of a point $($x$,$y$)$ from $($x$,$ yc$)$ is: $($x $-$ X$)*+($y $-$ yo$)*$

o Apoint $($x$,$y$)$ is within the circle when: $($x$-$x$2+($y$-$y$)2$sr$?$

o Avertical line x $=$ a crosses the circle when: $($a$-$ X $<$ I

o Ahorizontal line y $=$ b crosses the circle when: $($b$-$y$)?$sr$?$

In your implementation you can use any of the standard generic ADTs:

Stack MaxPriorityQueue$>$

Queue MinPriorityQueue$>$

$\_$ SymbolTable,Value$>$

L $\{1\{]$

XSCH$3150$

Where Comparabie is the following generic Java interface:

public interface Comparable

int compareTo$($T o$)|$ Compares this object with the specified object o$.$ It returns

a negative integer if $$this is less than $0,$ a positive integer

if $$this is greater than o$,$ and zero if $$this is equal to $0.$

You do not need to implement the ADTs you use, but for each one you use you should specify:

$00$

$*$ An API for the ADT, containing the methods you use in your implementation.

$*$ Atight asymptotic upper bound of the worst$-$case running time of each of the ADT

methods.

$*$ A brief English description of a known implementation of the ADT that has the running

time properties you specified above.

Note: class Point does not implement the Comparable interface. You need to define an

additional PointFromCentre class to use as Key in these ADTs. This new class should be able

to compare points with respect to their proximity to a centre point.

C $\{]$