Set-valued recursions arising from vantage-point trees

We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body $K$ in $({\mathbb{R}}^d,\mathrm{\parallel }\cdot \mathrm{\parallel })$, where $\mathrm{\parallel }\cdot \mathrm{\parallel }$ is an arbitrary norm on ${\mathbb{R}}^d$. We prove that a sequence of sets, associated with the left boundary of a vantage-point tree, forms a recurrent Harris chain on the space of convex bodies in $({\mathbb{R}}^d,\mathrm{\parallel }\cdot \mathrm{\parallel })$. The limiting object is a ball polyhedron, that is, an a.s.~finite intersection of closed balls in $({\mathbb{R}}^d,\mathrm{\parallel }\cdot \mathrm{\parallel })$ of possibly different radii. As a consequence, we derive a limit theorem for the length of the leftmost path of a vantage-point tree.