<p>We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body <i>K</i> in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(\mathbb {R}^d,\Vert \cdot \Vert )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> <mo>,</mo> <mo stretchy="false">‖</mo> <mo>·</mo> <mo stretchy="false">‖</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Vert \cdot \Vert $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">‖</mo> <mo>·</mo> <mo stretchy="false">‖</mo> </mrow> </math></EquationSource> </InlineEquation> is an arbitrary norm on <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathbb {R}^d$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$(\mathbb {R}^d,\Vert \cdot \Vert )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> <mo>,</mo> <mo stretchy="false">‖</mo> <mo>·</mo> <mo stretchy="false">‖</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. The limiting object is a ball polyhedron, that is, an a.s. finite intersection of closed balls in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(\mathbb {R}^d,\Vert \cdot \Vert )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> <mo>,</mo> <mo stretchy="false">‖</mo> <mo>·</mo> <mo stretchy="false">‖</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of possibly different radii. As a consequence, we derive a limit theorem for the length of the leftmost path of a vantage-point tree.</p>

Set-Valued Recursions Arising from Vantage-Point Trees

期刊论文
出版模式：

开放获取
发表日期：

2025年1月23日

查看全文

Congzao Dong,
Alexander Marynych,
Ilya Molchanov

摘要

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