# Pick a point, any point…

You are handed a compact convex set $A\subset \mathbb R^n$ and asked to pick a point in it. Let $s(A)$ denote the point you selected in $A$. You can choose it in any way you want. But please be consistent: if $\phi$ is a isometry of $\mathbb R^n$, your choice in $\phi(A)$ should be $\phi(s(A))$. And please respect the additive structure: the sum of two convex sets is another convex set $A+B=\lbrace a+b\colon a\in A, b\in B\rbrace$, and we want $s(A+B)=s(A)+s(B)$.

The conditions look reasonable, yet it is not immediately clear if they can be satisfied. But they can, and in a unique way: $s(A)$ must be the Steiner point of $A$, defined as follows.

Given a unit vector $v$, let $h_A(v)=\sup_{x\in A} \langle x,v \rangle$. This defines the support function $h_A\colon S^{n-1}\to\mathbb R$, which completely describes the convex set. Note that $h_{A+B}=h_A+h_B$. The Steiner point is

$\displaystyle s(A)=2\int_{S^{n-1}} h_A(v)\,v \, d\sigma(v)$

where $\sigma$ is the normalized surface measure on the unit sphere $S^{n-1}$. The factor of 2 is necessary to achieve $s(\{a\})=a$, the underlying reason being that the average of $\cos^2$ is $1/2$. The additivity $s(A+B)=s(A)+s(B)$ is obvious. Applying it with $B=\{b\}$, we observe that $s$ commutes with translations. That it also commutes with rotations (the orthogonal group) follows, via the change of variables, from $h_{UA}(v)=h_{A}(U^{-1}v)$.

One can interpret $s(A)$ as a bounded linear operator on the space $C(S^{n-1})$. That is, $|s(A)-s(B)|\le L\sup|h_A-h_B|$. What is $\sup|h_A-h_B|$ anyway? It’s the infimal number $r$ such that $h_A\le h_B+r$ and $h_B\le h_A+r$. But the constant $r$ is the support function of the ball $\mathbb B_r=\{x\colon |x|\le r\}$. Hence, $\sup|h_A-h_B|$ is the infimal $r$ such that $A\subset B+\mathbb B_r$ and $B\subset A+\mathbb B_r$; in other words, the Hausdorff distance between $A$ and $B$.

To summarize:

1. the Steiner point performs a Lipschitz selection from compact convex sets;
2. it is the unique selection which commutes with isometries and addition;
3. it also has the smallest Lipschitz constant among all Lipschitz selections.

(I did not prove 2 and 3 here.)

Here is my Sage code that defines the support function and the Steiner point of the convex hull of a given point set; everything is in the plane.

def support(points,angle):
return max(map(lambda (a,b): a*cos(angle)+b*sin(angle), points))

def steiner(points):
x = numerical_integral(lambda t: (1/pi)*cos(t)*support(points,t), 0, 2*pi)[0]
y = numerical_integral(lambda t: (1/pi)*sin(t)*support(points,t), 0, 2*pi)[0]
return (x,y)


The code below calls steiner() with a random set of points. Of course, only the extreme points of the convex hull affect the outcome of computation.

myRange = IntegerRange(-5,6)
pts = [(myRange.random_element(),myRange.random_element()) for i in range(5)]
g1 = points(pts)
g2 = point(steiner(pts),color='red')
show(g1+g2)


Here is a sample output.

And since I published this Sage worksheet, you can go and play with it. No installation is required. In fact, sagenb.org is faster than the “local” Sage that lives in a Virtual Box inside of my (stupid and slow) Windows box.