Set-valued recursions arising from vantage-point trees

2023/12/09 by Congzao Dong, Dong, Congzao, Alexander Marynych +3
Mathematics · #60J05 #68P10 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Primary: 60D05 #Probability (math.PR) #Secondary: 60C05 #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2312.05651

openalex publication_date 2023/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body K in (ℝ^d,‖⋅‖), where ‖⋅‖ is an arbitrary norm on ℝ^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 (ℝ^d,‖⋅‖). The limiting object is a ball polyhedron, that is, an a.s.~finite intersection of closed balls in (ℝ^d,‖⋅‖) of possibly different radii. As a consequence, we derive a limit theorem for the length of the leftmost path of a vantage-point tree.

Related

• Spherical Recurrence and locally isometric embeddings of trees into positive density subsets of ℤ^d
• Permutations of point sets in ℝ^d
• Hoppe trees, random recursive sets and their barycentre
• Degree Distributions in Recursive Trees with Fitnesses
• Random points, convex bodies, lattices