k-d Tree

Usage notes

In this exercise we build the first branch of a k-d searching tree for the following 6 points in

(We use Maple notation.)

X = [[-4,3],[-2,2],[5,5],[7,3],[4,-4],[5,-6]]

Write a small Maple program in the Maple frontend or in your local Maple to compute the covariance matrix and copy the values of

below:
(Write exact values using fractions)

___________________

Using the Maple command Eigenvals compute the eigenvalues

of the covariance matrix

___________________

___________________

(To get an example to see how to use Eigenvals type ?Eigenvals in Maple)

Which eigenvalue

do we choose to split the points in two groups?

With the command Eigenvals used in b) you can also compute the eigenvectors. Write down the eigenvector

corresponding to the eigenvalue chosen in c) normalized to 1 (use exact values; in Maple the square root is computed with the command sqrt(), use it)

___________________

___________________
or

___________________

Now you can write down the equation of the straight line splitting the points. (The splitting line is given by

, where

is the eigenvector,

and

is a threshold. Computing

is equivalent to finding the median of

)

y = ___________________

Home

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.