Set-valued recursions arising from vantage-point trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917875148652544 |
|---|---|
| author | Dong, Congzao Marynych, Alexander Molchanov, Ilya |
| author_facet | Dong, Congzao Marynych, Alexander Molchanov, Ilya |
| contents | We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body $K$ in $(\mathbb{R}^d,\|\cdot\|)$, where $\|\cdot\|$ 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,\|\cdot\|)$. The limiting object is a ball polyhedron, that is, an a.s.~finite intersection of closed balls in $(\mathbb{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_05651 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Set-valued recursions arising from vantage-point trees Dong, Congzao Marynych, Alexander Molchanov, Ilya Probability Data Structures and Algorithms Primary: 60D05, Secondary: 60C05, 60J05, 68P10 We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body $K$ in $(\mathbb{R}^d,\|\cdot\|)$, where $\|\cdot\|$ 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,\|\cdot\|)$. The limiting object is a ball polyhedron, that is, an a.s.~finite intersection of closed balls in $(\mathbb{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. |
| title | Set-valued recursions arising from vantage-point trees |
| topic | Probability Data Structures and Algorithms Primary: 60D05, Secondary: 60C05, 60J05, 68P10 |
| url | https://arxiv.org/abs/2312.05651 |