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).


1 Answer 1


This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed quadtree. Anyway, the currents bounds known are

$O(n/\varepsilon^d)$: total size

$d^{O(1)} \log n$: query time

See this paper: https://dl.acm.org/doi/10.1145/509907.510011

These authors had extensive followup work on trading query time for space, etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.