Describing convex hulls in purely metrical terms

Question

Let $X$ denote a Euclidean space; take $X = \mathbb{R}^n$ for concreteness. Now consider $x,y \in X$. Then the line segment joining $x$ and $y,$ hereafter denoted $[x,y]$, can be described in algebraic terms as the set of all possible convex combinations of $x$ and $y$. That is, $[x,y]$ is the convex hull of $\{x,y\}$. This line segment can also be described in geometric terms as the set of all points that minimizes the sum of distances to $x$ and $y$. Symbolically:

$$[x,y] = \mathop{\mathrm{arg}\,\mathrm{min}}_{p:X}\left( d(p,x)+d(p,y)\right)$$

Now suppose we have $3$ points, $x,y$ and $z$. Then their convex hull is a (filled-in) triangle. I'd like to describe this triangle as the set of all points minimizing something. The expression

$$(*) \qquad \mathop{\mathrm{arg}\,\mathrm{min}}_{p:X}\left( d(p,x)+d(p,y)+d(p,z)\right)$$

doesn't do the trick, since this is just the Fermat point of the triangle under question. Sum of squares doesn't work, either.

Question. Does there exist a function $f : \mathbb{R}_{\geq 0}^3 \rightarrow \mathbb{R}_{\geq 0}$ such that for all Euclidean spaces $X$ and all $x,y,z \in X$, the convex hull of $\{x,y,z\}$ equals the following? $$\qquad \mathop{\mathrm{arg}\,\mathrm{min}}_{p:X}f(d(p,x),d(p,y),d(p,z))$$

Answer 1

That would be really cool. But there is no such function, even for triples of points in $\mathbb{R}^1$.

Indeed, take a triple $(a,b,c)$ of positive numbers. Let $x=-a$, $y=b$, $z=c$. The point $t=0$ is an interior point of the convex hull, and has distances $a,b,c$ to the points $x,y,z$. Consider moving $t$ slightly to the left or to the right of $0$: it stays within the convex hull, so the function $f$ does not change. Conclusion:

• $f$ is constant on lines with the direction vector $\langle 1,1,-1\rangle$, as well as (by symmetry) $\langle 1,-1,1\rangle$ and $\langle -1,1,1\rangle$.

This implies that $f$ is identically constant, because one can go from $(a,b,c)$ to any other point $(a',b',c')$ moving along such lines. Indeed, the combination $$ (a,b,c)+\epsilon(1,1,-1)+\epsilon(1,-1,1) = (a+2\epsilon,b,c) $$ enables one to move along the first coordinate axis, and similarly for others.

---

If the collinear triples are excluded, the situation doesn't change. One can slightly perturb the triple $x=-a$, $y=b$, $z=c$ to make it non-collinear; moving $t$ along a line as before, conclude that $f$ is constant on certain almost-linear curves. Put together short pieces of such curves to move around in the $3$-space.

Answer 2

An analogous formula for triangles is $$ \operatorname{conv}\ \{x,y,z\} = \mathop{\operatorname{arg min}}_p\ (A(x,y,p) + A(x,p,z) + A(p,y,z)) $$ where $A(a,b,c)$ denotes the area of the triangle with vertices $a,b,c$.

Not quite what you wanted, but there it is. If you really want distances only, perhaps you could compute the areas by Heron's formula.

---

A proof, you say? Well... no, I haven't worked out a proof in detail. Let me sketch some ideas that could probably be turned into a proof or two with some effort.

First, that formula doesn't work when $x,y,z$ are collinear; let's just assume they're not.

Other than that, it's the same idea as in the one-dimensional case: if $p$ is outside the triangle then the triangles whose areas we compute overlap, so we double-count, but if $p$ is inside then we get exactly $A(x,y,z)$. To do it formally, I think the major ingredients would be (1) reduction to the case where $p$ is in the affine hull of $x,y,z$ (if it's not, its projection $p'$ onto that plane makes lesser areas), and (2) Radon's theorem and some analysis of cases (to verify that we do get double counting whenever $p$ is outside).

Alternatively... I bet there's some slick way where we embed the plane in $\mathbb R^3$ as the plane $x_3=1$, take the triangles to correspond to tetrahedra (with fourth vertex at the origin), relate the areas of those triangles to the volumes of those tetrahedra, and write out everything in $3\times 3$ determinants. Then, I bet, you'll find that there's an expression like $A(x,y,p)+A(x,p,z)+A(p,y,z)$ except with alternating signs, computing the volume of the convex hull of the origin and the four points in the plane, using determinants as signed areas. Obviously the volume of that solid is minimized when $p$ is inside $xyz$, and since we take absolute values, we get an even larger number... Well, like I said, I haven't worked out the details, but I bet this would work.