Structure of average distance minimizers in general dimensions
Lucas O’Brien, Forest Kobayashi, Young-Heon Kim · 2025
Read Structure of average distance minimizers in general dimensions by Lucas O’Brien, Forest Kobayashi, Young-Heon Kim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23256.txt.
Introduction
Lucas O'Brien, Forest Kobayashi, and Young-Heon Kim describe the shape of the cheapest connected network for a spread-out demand. Their 2025 paper studies the average distance problem: given a probability distribution over space, find the short connected set that minimizes the average powered distance to it. The problem dates to 2002 and models roads, pipes, and supply lines at once.
Their tool is the barycentre field, a flow-like object attached to any candidate set. With it they give a complete topological description of the minimizers for two ranges of the power, crucially including dimensions above two for the first time. The shape of optimal infrastructure is a theorem here, not a guess.
Catalog record
| CREATOR | Lucas O’Brien, Forest Kobayashi, Young-Heon Kim |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23256
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structure of average distance minimizers in general dimensions Thanks: LO is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Undergraduate Student Research Award. FK is supported by the doctoral fellowship of the University of British Columbia. YHK is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), with Discovery Grant RGPIN-2019-03926, as well as Exploration Grant (NFRFE-2019-00944) from the New Frontiers in Research Fund (NFRF). YHK is also a member of the Kantorovich Initiative (KI), which is supported by the PIMS Research Network (PRN) program of the Pacific Institute for the Mathematical Sciences (PIMS). We thank PIMS for their generous support. Part of this work was completed during YHK’s visit at the Korea Advanced Institute of Science and Technology (KAIST), and we thank them for their hospitality and the excellent environment. ©2025 by the authors. All rights reserved. Lucas O’Brien, Forest Kobayashi, Young-Heon Kim Abstract . For a fixed, compactly supported probability measure μ \mu on the d d -dimensional space ℝ d \mathbb{R}^{d} , we consider the problem of minimizing the p th p^{\mathrm{th}} -power average distance functional over all compact, connected Σ ⊆ ℝ d \Sigma\subseteq\mathbb{R}^{d} with Hausdorff 1-measure ℋ 1 ( Σ ) ≤ l \mathcal{H}^{1}(\Sigma)\leq l . This problem, known as the average distance problem, was first studied by Buttazzo, Oudet, and Stepanov in 2002, and has undergone a considerable amount of research since. We will provide a novel approach to studying this problem by analyzing it using the so-called barycentre field considered previously by Hayase and two of the authors. This allows us to provide a complete topological description of minimizers in arbitrary dimensions when p = 2 p=2 and p > 1 2 ( 3 + 5 ) ≈ 2.618 p>\frac{1}{2}(3+\sqrt{5})\approx 2.618 , the first such result that includes the case when d > 2 d>2 . 1. Introduction Suppose one has been tasked with constructing a network \Sigma of water pipes for a city in which demand is distributed according to a given probability measure \mu and the construction costs are modelled by a given functional {C}(\Sigma) . Given a fixed budget l , how can one determine the best possible network shape \Sigma ? To be more specific, let \mu be a probability measure on \mathbb{R}^{d} , that is, \mu\in\mathcal{P}(\mathbb{R}^{d}) , where d\geq 1 . Suppose that for fixed p\geq 1 , each “client” x\in\supp\mu has to pay a price \mathrm{dist}^{p}(x,\Sigma) to connect to the network \Sigma . Then, the best network \Sigma should be the one minimizing the \mu -average cost J_{p}(\Sigma)=\int_{\mathbb{R}^{d}}\mathrm{dist}^{p}(x,\Sigma)\,\mathrm{d}\mu(x). The choice of different values for p\geq 1 affects the proportional weighting of outliers in \mathrm{dist}(x,\Sigma) , and for us the main case is p=2 . The problem may now be stated succinctly as: (1.1) \begin{cases}\text{Minimize:}\quad&J_{p}(\Sigma)\\ \text{Subject to:}\quad&C(\Sigma)\leq l.\end{cases} The choice of constraint functional C greatly impacts the qualitative traits of solutions to ( 1.1 ) as well as the analysis required to characterize them. Broadly, the two categories one typically considers are “intrinsic” constraints such as \mathcal{H}^{1}(\Sigma) and “extrinsic” constraints such as \mathrm{arclength}(\gamma) , where \gamma:[0,1]\to\mathbb{R}^{d} parametrizes \Sigma . We briefly discuss some references for different formulations in Section 1.2 . In this paper we consider the average distance problem (ADP), also called the irrigation problem , which was first introduced by Buttazzo, Oudet, and Stepanov in 2002 [ 5 ] : (ADP) \begin{cases}\text{Minimize:}\quad&J_{p}(\Sigma)\\ \text{Subject to:}\quad&\Sigma\text{ is compact and connected, and }\mathcal{H}^{1}(\Sigma)\leq l.\end{cases} For the ( ADP ), a longstanding problem of interest—which we address in this paper—is characterizing the topology of optimizers. A chronology of progress on the topological characterization problem can be found in the survey [ 21 ] ; let us briefly summarize the main points. The first topological characterization result for the ( ADP ) was obtained by Buttazzo and Stepanov in 2003 [ 6 ] . In that work they proved for d=2 that if \mu\ll\mathrm{Lebesgue} and has a density that is L^{q} for some q>4/3 , then optimizers of the ( ADP ) are (topological) finite, binary trees . That is, optimizers contain no loops, are comprised of finitely many “branches” (homeomorphic copies of intervals), and the branches only meet in triple junctions. In 2004, Paolini and Stepanov proved the absence of loops in general dimensions d\geq 2 [ 26 , Theorem 5.6] under only a mild regularity assumption on \mu ; namely, that if \Sigma is optimal then \mu(\Sigma)=0 . However, the finitely-many branches and triple junction results remained unknown. In 2006, Stepanov [ 29 ] established the following “conditional” topological characterization for d\geq 2 . For fixed \Sigma , let \pi_{\Sigma} denote any measurable selection of the closest point projection onto \Sigma . Let \Sigma be an optimizer, and suppose (a) that \mu(\Sigma)=0 , and (b) that (1.2) \text{ the pushforward measure }\nu\coloneqq(\pi_{\Sigma})_{\#}\mu\text{ contains an atom.} Then, by [ 29 , Theorem 5.5] , \Sigma is a finite, binary tree. As we do not know the optimizer a priori, Stepanov’s hypothesis (a) is effectively equivalent to the condition that (1.3) \mu(A)=0 for each set A\subseteq\mathbb{R}^{d} with \mathcal{H}^{1}(A)<\infty. The hypothesis ( 1.3 ) is essentially sharp: If \supp\mu is a 1-d set and l\geq\mathcal{H}^{1}(\supp\mu) , then for all optimizers \Sigma one has \supp\mu\subseteq\Sigma ; thus if \supp\mu contains at least one of \{\text{a loop},\ \text{infinitely-many branches},\ \text{more-than-triple junctions}\} then \Sigma will too. In this way, Stepanov’s result [ 29 , Theorem 5.5] reduces the topological characterization question to proving the existence of an atom of \nu . Such existence seems, intuitively, quite plausible, since “ \Sigma has no loops” [ 26 , Theorem 5.6] implies “ \Sigma has endpoints,” and (as noted in the discussion following [ 21 , Lemma 7] ) we would expect those “endpoints” to receive positive mass in \nu . Despite this intuitive picture, in dimensions d>2 , the existence of an atom result has remained elusive in the ensuing years. Hence, the full topological characterization has remained open—though, seemingly, tantalizingly close—in dimensions d>2 . 1.1. Key Contributions of Our Paper In this work, we resolve the topological characterization problem in general dimensions d\geq 2 for most values of p\geq 2 , including p=2 . This is our first main theorem: Theorem 1.1 (see Theorem 3.9 for a more precise statement) . Let d\geq 2 and let p=2 or p>\frac{1}{2}(3+\sqrt{5}) . Assume ( 1.3 ) and let \Sigma_{\rm opt} be a solution to the ( ADP ). Then, (a) \Sigma_{\rm opt} does not contain any loops and is thus a topological tree, (b) \Sigma_{\rm opt} has only finitely many endpoints and branching points, and (c) each branching point is a triple junction. Note that part (a) was already proven in [ 26 ] *Theorem 5.6. Our approach centers on establishing the missing link that turns Stepanov’s conditional result [ 29 ] *Theorem 5.5 into a general one: Namely, that for each optimal \Sigma , the measure \nu contains an atom ( 1.2 ). To obtain this result, the key insight is to view the problem from the perspective of the barycentre field ( Definition 2.9 ), which was considered previously by Hayase and two of the authors in [ 18 ] in studying a version of