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')

Here is a sample output.

Steiner point (Sage)

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.

Leave a Reply


WordPress.com Logo


Twitter picture


Facebook photo


Google+ photo


Connecting to %s