Nearest Neighbors Search

Usage notes

The k-d tree for the following point

is given by the

and

as follows:

We look for the 3 NN (Nearest Neighbours) to the point (6, -5) and use the search algorithm given in paragraph 2.6.3.1 (online lecture)

a)

We start with a search radius hhigh = 1. Which value has hhigh at the end of the exponential search?
___________________

b)

During these calls to NNsearch, how many times is left(T) explored?
___________________

and right(T) ?
___________________

and left(left(T)) ?
___________________

and right(left(T)) ?
___________________

and left(right(T)) ?
___________________

and right(right(T)) ?
___________________

c)

Consider the bisection search of the search algorithm (the second loop). Which are the starting values of hlow and hhigh?
hlow = ___________________ hhigh = ___________________

And after the first cycle?
hlow = ___________________ hhigh = ___________________

And after the end of the loop?
h = ___________________

What is the exit condition of the second loop in our example?

The loop condition is no longer satisfied.

There is a RETURN call.

d)

The solution. Give the solution:
(format: (x1,y1),(x2,y2),(x3,y3))
___________________

Home

Feedback to quiz developers, problem reports...please use it!!!

Name:
	Restore previous session, if applicable Start blank quiz
Note:	If you wish to ask for a hint or a solution, or if you want your answers checked, you have to log in. Your answers, or the fact that you asked for a hint or solution, may be recorded.