You are handed a compact convex set and asked to pick a point in it. Let denote the point you selected in . You can choose it in any way you want. But please be consistent: if is a isometry of , your choice in should be . And please respect the additive structure: the sum of two convex sets is another convex set , and we want .
The conditions look reasonable, yet it is not immediately clear if they can be satisfied. But they can, and in a unique way: must be the Steiner point of , defined as follows.
Given a unit vector , let . This defines the support function , which completely describes the convex set. Note that . The Steiner point is
where is the normalized surface measure on the unit sphere . The factor of 2 is necessary to achieve , the underlying reason being that the average of is . The additivity is obvious. Applying it with , we observe that commutes with translations. That it also commutes with rotations (the orthogonal group) follows, via the change of variables, from .
One can interpret as a bounded linear operator on the space . That is, . What is anyway? It’s the infimal number such that and . But the constant is the support function of the ball . Hence, is the infimal such that and ; in other words, the Hausdorff distance between and .
- the Steiner point performs a Lipschitz selection from compact convex sets;
- it is the unique selection which commutes with isometries and addition;
- 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) y = numerical_integral(lambda t: (1/pi)*sin(t)*support(points,t), 0, 2*pi) 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.