{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T18:01:48Z","timestamp":1780164108922,"version":"3.54.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People\u2019s Republic of China","doi-asserted-by":"publisher","award":["DL2022174005L"],"award-info":[{"award-number":["DL2022174005L"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study vantage-point trees constructed using an independent sample from the uniform distribution on a fixed convex body\n                    <jats:italic>K<\/jats:italic>\n                    in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(\\mathbb {R}^d,\\Vert \\cdot \\Vert )$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Vert \\cdot \\Vert $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is an arbitrary norm on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathbb {R}^d$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>R<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . 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\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(\\mathbb {R}^d,\\Vert \\cdot \\Vert )$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The limiting object is a ball polyhedron, that is, an a.s.\u00a0finite intersection of closed balls in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(\\mathbb {R}^d,\\Vert \\cdot \\Vert )$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mo>\u2016<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of possibly different radii. As a consequence, we derive a limit theorem for the length of the leftmost path of a vantage-point tree.\n                  <\/jats:p>","DOI":"10.1007\/s00454-024-00714-1","type":"journal-article","created":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T13:30:44Z","timestamp":1737639044000},"page":"1134-1150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Set-Valued Recursions Arising from Vantage-Point Trees"],"prefix":"10.1007","volume":"75","author":[{"given":"Congzao","family":"Dong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Marynych","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2502-0334","authenticated-orcid":false,"given":"Ilya","family":"Molchanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,1,23]]},"reference":[{"key":"714_CR1","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/054","volume-title":"A Course in Convexity","author":"A Barvinok","year":"2002","unstructured":"Barvinok, A.: A Course in Convexity. Amer. Math. Soc., Providence (2002)"},{"issue":"9","key":"714_CR2","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J Bentley","year":"1975","unstructured":"Bentley, J.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"714_CR3","volume-title":"Convergence of Probability Measures","author":"P Billingsley","year":"2013","unstructured":"Billingsley, P.: Convergence of Probability Measures. Wiley, London (2013)"},{"issue":"4","key":"714_CR4","doi-asserted-by":"publisher","first-page":"413","DOI":"10.15559\/21-VMSTA188","volume":"8","author":"V Bohun","year":"2021","unstructured":"Bohun, V.: Probabilistic analysis of vantage point trees. Modern Stoch. Theory Appl. 8(4), 413\u2013434 (2021)","journal-title":"Modern Stoch. Theory Appl."},{"key":"714_CR5","unstructured":"Bohun, V.: Asymptotic properties of random trees (in Ukrainian). Ph.D. Thesis, Taras Shevchenko National University of Kyiv (2022). Available at https:\/\/ir.library.knu.ua\/handle\/123456789\/2151"},{"key":"714_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"2010","unstructured":"Durrett, R.: Probability: Theory and Examples, 4th edn. Cambridge University Press, Cambridge (2010)","edition":"4"},{"key":"714_CR7","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/PL00010672","volume":"9","author":"AWC Fu","year":"2000","unstructured":"Fu, A.W.C., Chan, P.M.S., Cheung, Y.L., Moon, Y.S.: Dynamic vp-tree indexing for $$n$$-nearest neighbor search given pair-wise distances. VLDB J. 9, 154\u2013173 (2000)","journal-title":"VLDB J."},{"issue":"12","key":"714_CR8","doi-asserted-by":"publisher","first-page":"8823","DOI":"10.1090\/tran\/6620","volume":"368","author":"P Kevei","year":"2016","unstructured":"Kevei, P., V\u00edgh, V.: On the diminishing process of B\u00e1lint T\u00f3th. Trans. Am. Math. Soc. 368(12), 8823\u20138848 (2016)","journal-title":"Trans. Am. Math. Soc."},{"issue":"05","key":"714_CR9","doi-asserted-by":"publisher","first-page":"1550003","DOI":"10.1142\/S0219199715500030","volume":"17","author":"I Molchanov","year":"2015","unstructured":"Molchanov, I.: Continued fractions built from convex sets and convex functions. Commun. Contemp. Math. 17(05), 1550003 (2015)","journal-title":"Commun. Contemp. Math."},{"key":"714_CR10","unstructured":"Moore, A.: An introductory tutorial on kd-trees. Technical Report No. 209, Computer Laboratory, University of Cambridge, Carnegie Mellon University, Pittsburgh (1991). https:\/\/www.ri.cmu.edu\/pub_files\/pub1\/moore_andrew_1991_1\/moore_andrew_1991_1.pdf"},{"key":"714_CR11","doi-asserted-by":"crossref","unstructured":"Nielsen, F., Piro, P., Barlaud, M.: Bregman vantage point trees for efficient nearest neighbor queries. In: 2009 IEEE International Conference on Multimedia and Expo, pp.\u00a0878\u2013881 (2009)","DOI":"10.1109\/ICME.2009.5202635"},{"key":"714_CR12","unstructured":"Omohundro, S.: Five balltree construction algorithms. Technical Report, 89-063 (1989). http:\/\/www.icsi.berkeley.edu\/ftp\/global\/pub\/techreports\/1989\/tr-89-063.pdf"},{"key":"714_CR13","volume-title":"Convex Bodies: the Brunn\u2013Minkowski Theory","author":"R Schneider","year":"2014","unstructured":"Schneider, R.: Convex Bodies: the Brunn\u2013Minkowski Theory, 2nd edn. Cambridge University Press, Cambridge (2014)","edition":"2"},{"issue":"194","key":"714_CR14","first-page":"311","volume":"93","author":"PN Yianilos","year":"1993","unstructured":"Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda 93(194), 311\u2013321 (1993)","journal-title":"In Soda"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00714-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00714-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00714-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T17:49:10Z","timestamp":1780163350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00714-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,23]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["714"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00714-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,23]]},"assertion":[{"value":"28 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}