Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $y_i \le c$. Every leaf of $T$ is associated with exactly one of the $n$ points.
For any new point $y \in \mathbb{R}^d$, we write $x(y)$ for the point associated with the leaf that $y$ ends up in.
The aim is to construct $T$ such that $x(y)$ is a good guess of the point that is closest to $y$, i.e. we want to find $T$ such that for any $y \in \mathbb{R}^d$
$$\|y - x(y)\|_2 \le (1+\epsilon) \min_{j \in [n]} \|x_j - y\|_2$$ for some small $\epsilon > 0$.
Naturally, the larger $L$ the smaller $\epsilon$ may become. And the easier it is to separate the points $x_1,...,x_n$ with a tree, the smaller $L$ may be.
My Questions:
- What is an algorithm that performs this task?
- In particular, given $n,d,\epsilon$, are there worst-case bounds on how many leaves $L$ we need?
- The other way around, given $L, n, d$, what can we say about $\epsilon$?
Of course, even for just $n=2$ points, we can only hope for an approximate solution since the set $\Big\{\|y-x_1\| = \|y-x_2\| \Big\}$ will be a general hyperplane (and is thus not axis aligned).
