A sharp p p -subadditive bound for the l p l_{p} Hausdorff distance from convex hull
Mark Meyer · 2026
Read A sharp p p -subadditive bound for the l p l_{p} Hausdorff distance from convex hull by Mark Meyer (2026) 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-2604-20387.txt.
Introduction
Meyer settles the best constant for a p-subadditive bound on the l_p Hausdorff distance. That distance measures how far a compact set in the plane sits from its convex hull, the smallest convex shape containing it. For any two nonempty compact planar sets, the distance of their sum, raised to the p power, stays below a constant times the sum of the two distances raised to p. He proves the sharp constant equals the larger of 1 and 2 raised to p minus 2, so no smaller constant works in general.
Catalog record
| CREATOR | Mark Meyer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125256 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20387
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A sharp p p -subadditive bound for the l p l_{p} Hausdorff distance from convex hull Mark Meyer Abstract . We study the l p l_{p} Hausdorff distance from convex hull of a compact set A ⊂ ℝ n A\subset\mathbb{R}^{n} , which is the distance d ( l p ) ( A ) := sup x ∈ conv ( A ) inf a ∈ A ‖ x − a ‖ p , d^{(l_{p})}(A):=\sup_{x\in\textup{conv}(A)}\inf_{a\in A}\|x-a\|_{p}, where ∥ ⋅ ∥ p \|\cdot\|_{p} is the l p l_{p} -norm on ℝ n \mathbb{R}^{n} . We prove that when n = 2 n=2 and 1 ≤ p < ∞ 1\leq p<\infty , the function ( d ( l p ) ) p (d^{(l_{p})})^{p} is subadditive with respect to Minkowski summation, up to multiplication by the factor max { 1 , 2 p − 2 } \max\{1,2^{p-2}\} , and we observe that this bound is sharp. 1. Introduction 1.1. Sharp l_{p} -bound For a parameter 1\leq p\leq\infty , the l_{p} - Hausdorff distance from convex hull of a nonempty compact set A\subset\mathbb{R}^{n} is the distance (1) d^{(l_{p})}(A):=\sup_{x\in\textup{conv}(A)}\inf_{a\in A}\|x-a\|_{p}, where \textup{conv}(A) is the convex hull of the set A , and \|\cdot\|_{p} is the l_{p} -norm on \mathbb{R}^{n} . Intuitively, the value d^{(l_{p})}(A) is the farthest possible l_{p} -distance to the set A from a point in the convex hull of A . In fact, the name Hausdorff distance originates from the fact the quantity d^{(l_{2})}(A) is exactly the distance between the set A and and its convex hull, measured by the Hausdorff metric. The Minkowski sum of nonempty compact sets A,B\subset\mathbb{R}^{2} is the set A+B:=\{a+b:a\in A,b\in B\}. The following theorem, which is the main result of this paper, establishes that the function (d^{(l_{p})})^{p} is subadditive (with respect to Minkowski summation) on nonempty compact sets in \mathbb{R}^{2} up to multiplication by a constant that depends on the parameter p . Theorem 1.1 . Let 1\leq p<\infty . Then the bound (2) d^{(l_{p})}(A+B)\leq\max\{1,2^{\frac{p-2}{p}}\}\sqrt[p]{(d^{(l_{p})}(A))^{p}+(d^{(l_{p})}(B))^{p}} holds for any nonempty compact sets A,B\subset\mathbb{R}^{2} . Moreover, the constant \max\{1,2^{\frac{p-2}{p}}\} is sharp in the following sense: (1) If 1\leq p\leq 2 , then for any nonnegative real numbers \alpha and \beta there exist nonempty compact sets A,B\subset\mathbb{R}^{2} such that d^{(l_{p})}(A)=\alpha , d^{(l_{p})}(B)=\beta , and ( 2 ) is equality. (2) If p>2 , then for any positive real number \alpha there exist nonempty compact sets A,B\subset\mathbb{R}^{2} such that d^{(l_{p})}(A)=d^{(l_{p})}(B)=\alpha and ( 2 ) is equality. The significance of Theorem 1.1 originates from the Shapley–Folkman–Starr theorem, whose original proof is in the appendix of the 1969 paper [ 13 ] of Starr. A 1969 paper of Emerson and Greenleaf observes the same phenomenon in the setting of open relatively compact sets [ 4 , Theorem 1.3] . The Shapely–Folkman–Starr theorem states that if A_{1},\dots,A_{m}\subset\mathbb{R}^{n} are nonempty compact sets, then we have the bound (3) (d^{(l_{2})}(A_{1}+\dots+A_{m}))^{2}\leq\sum_{\min(m,n)}\textup{rad}^{2}(A_{i}), where we take the summation on the right side over the largest \min(m,n) terms \textup{rad}(A_{i}) , and the term \textup{rad}(A):=\inf_{x\in\mathbb{R}^{n}}\sup_{a\in A}\|x-a\|_{2} is the outer radius of a compact set A . If each set A_{i} in ( 3 ) is the same set A , then for m\geq n we obtain the bound (4) d^{(l_{2})}\left(A(m)\right)\leq\frac{\sqrt{n}}{m}\cdot\textup{rad}(A), where A(m):=m^{-1}\sum_{i=1}^{m}A denotes the m th set average of the set A . We deduce from ( 4 ) that the sequence of m th set averages of a set A converges to \textup{conv}(A) in the Hausdorff metric as m tends to infinity. Some authors refer to this phenomenon as the convexification effect of Minkowski summation. The reader can reference the survey [ 5 ] of Fradelizi, Madiman, Marsiglietti, and Zvavitch for more information on this topic. On a related note, Dyn and Farkhi [ 3 , Page 5] conjectured in 2005 that for any nonempty compact A,B\subset\mathbb{R}^{n} the bound (5) (d^{(l_{2})}(A+B))^{2}\leq(d^{(l_{2})}(A))^{2}+(d^{(l_{2})}(B))^{2} holds. To see the significance of this conjecture in the context of the present discussion, we observe that if the bound ( 5 ) were true, then we could replace the term \textup{rad}(A) on the right side of ( 4 ) with the term d^{(l_{2})}(A) . This in turn would make an improvement on the right side of ( 4 ) due to the fact that d^{(l_{2})}(A)\leq\textup{rad}(A) . In 2018, Fradelizi, Madiman, Marsiglietti, and Zvavitch disproved the Dyn–Farkhi conjecture [ 5 , Theorem 7.3] in the case n\geq 3 . However, their counterexample relied on the construction of two two-dimensional sets whose sum is a three-dimensional set, and as a result the conjecture remained open for the case n=2 . Recent work [ 11 ] of the author confirmed the Dyn–Farkhi conjecture when n=2 , establishing an improvement of ( 4 ). In the present paper, we make further improvements on the techniques used in [ 11 ] to obtain Theorem 1.1 , which is the l_{p} analogue of the bound ( 5 ). We emphasize that the counterexample of Fradelizi, Madiman, Marsiglietti, and Zvavitch relies fundamentally on the fact that A\neq B , so the Dyn–Farkhi conjecture ( 5 ) remains open for the special case A=B when n\geq 3 . One may also ask whether ( 5 ) holds when n=1 , since we have only mentioned results for n\geq 2 . Not only is ( 5 ) true in the one-dimensional case, but it is possible to derive stronger bounds. For example, the reader may reference [ 10 , Lemma 2.4] for a sharp bound involving sums of two or more compact sets in \mathbb{R} , and [ 5 , Theorem 7.5] for strong fractional subadditive bounds, which in the case of n=1 hold for sums of two or more compact sets. In the following subsections, we highlight other interesting developments related to the Hausdorff distance from convex hull. 1.2. The convex hull of a sumset in \mathbb{R}^{2} A convex body K\subset\mathbb{R}^{n} is a set that is compact, convex, and has nonempty interior. A convex body K is symmetric if K=-K . The Minkowski functional of K is the function \|\cdot\|_{K}:\mathbb{R}^{n}\rightarrow[0,\infty) that satisfies (6) \|x\|_{K}:=\inf\{\lambda>0:x\in\lambda K\}. If K is a symmetric convex body, then the function \|\cdot\|_{K} is a symmetric norm on \mathbb{R}^{n} , so it makes sense to replace the norm \|\cdot\|_{p} in ( 1 ) with the norm \|\cdot\|_{K} to arrive at the generalized Hausdorff distance from convex hull (7) d^{(K)}(A):=\sup_{x\in\textup{conv}(A)}d^{(K)}(x,A), where we define d^{(K)}(x,A):=\inf_{a\in A}\|x-a\|_{K} to be the K -distance from the point x to the set A . The idea of the generalized Hausdorff distance from convex hull originates from the survey [ 5 , Section 7] . We begin with a generalization of a key lemma [ 11 , Lemma 3.8] that gives a characterization of the convex hull of the Minkowski sum of compact sets in \mathbb{R}^{2} . In the statement below, we refer to the K -length of an interval [a,b] , which is the difference \|a-b\|_{K} of the endpoints in the K -norm. Theorem 1.2 . Let K\subset\mathbb{R}^{2} be a symmetric convex body, and let A,B\subset\mathbb{R}^{2} be nonempty compact sets. If (8) x\in\textup{conv}(A+B)\cap(A+\textup{conv}(B))^{c}\cap(\textup{conv}(A)+B)^{c}, then x is contained in a parallelogram whose vertex set is contained in the sumset A+B , and whose sides have K -length at most 2d^{(K)}(A) and 2d^{(K)}(B) respectively (See Figure 1 ). We