Continuity of circumcenter and circumradius

For a bounded set {A} on the plane (or in any Euclidean space) one can define the circumcenter {c(A)} and circumradius {r(A)} as follows: {r(A)} is the smallest radius of a closed disk containing {A}, and {c(A)} is the center of such a disk. (Other terms in use: Chebyshev center and Chebyshev radius.)

Smallest disk covering the points
Smallest disk covering the points

The fact that {c(A)} is well-defined may not be obvious: what if there are multiple disks of radius {r(A)} that contain {A}? To investigate, introduce the farthest distance function {f_A(x) = \sup_{a\in A} |x-a|}. By definition, {c(A)} is where {f_A} attains its minimum. The function {f_A} is convex, being the supremum of a family of convex functions. However, that does not guarantee the uniqueness of its minimum. We have two issues here:

  • {x\mapsto |x-a|} is not strictly convex
  • the supremum of an infinite family of strictly convex functions can fail to be strictly convex (like {\sup_{1<p<2} x^p = x} on the interval {[0,1]}).

The first issue is resolved by squaring {f_A}. Indeed, {f_A^2} attains its minimum at the same place where {f_A} does, and {f_A(x)^2 = \sup_{a\in A} |x-a|^2} where each term {|x-a|^2} is strictly convex.

Also, we don’t want to lose strict convexity when taking the supremum over {a\in A}. For this purpose, we must replace strict inequality by something more robust. The appropriate substitute is strong convexity: a function {f} is strongly convex if there is {\lambda>0} such that {f(x)-\lambda |x|^2 } is convex. Let’s say that {f} is {\lambda}-convex in this case.

Since {|x-a|^2-|x|^2 = -2\langle x,a\rangle + |a|^2} is a convex (in fact linear) function of {x}, we see that {|x-a|^2} is {1}-convex. This property passes to supremum: subtracting {|x|^2} from the supremum is the same as subtracting it from each term. Strong convexity implies strict convexity and with it, the uniqueness of the minimum point. So, {c(A)}, the minimum of {f_A^2}, is uniquely defined. (Finding it in practice may be difficult. The spherical version of this problem is considered in Covering points with caps).

Having established uniqueness, it is natural to ask about stability, or more precisely, the continuity of {c(A)} and {r(A)} with respect to {A}. Introduce the Hausdorff distance {d_{\mathcal H}} on the set of bounded subsets. By definition, {d_{\mathcal H}(A,B)\le \delta} if {A} is contained in {\delta}-neighborhood of {B}, and {B} is contained in {\delta}-neighborhood of {A}. It is easy to see that {r(B)\le r(A) + d_{\mathcal H}(A,B)}, and therefore

\displaystyle  |r(A)-r(B)|\le d_{\mathcal H}(A,B)

In words, the circumradius is a {1}-Lipschitz function of the set.

What about the circumcenter? If the set {A} is shifted by {d} units in some direction, the circumcenter moves by the same amount. So it may appear that it should also be a {1}-Lipschitz function of {A}. But this is false.

Observe (or recall from middle-school geometry) that the circumcenter of a right triangle is the midpoint of its hypotenuse:

Circumcenter of right triangle
Circumcenter of a right triangle

Consider two right triangles:

  • Vertices {(-1,0), (1,0), (1,\epsilon)}. The right angle is at {(1,0)}, and the circumvcenter is the midpoint of opposite side: {(0,\epsilon/2)}.
  • Vertices {(-1,0), (1,0), (\sqrt{1-\epsilon^2},\epsilon)}. The right angle is at
    {(\sqrt{1-\epsilon^2},\epsilon)} and the circumcenter is at {(0,0)}.

The Hausdorff distance between these two triangles is merely {1-\sqrt{1-\epsilon^2} < \epsilon^2}, yet the distance between their circumcenters is {\epsilon/2}. So, Lipschitz continuity fails, and the most we can hope for is Hölder continuity with exponent {1/2}.

And indeed, the circumcenter is locally {1/2}-Hölder continuous. To prove this, suppose {|c(A)-c(B)|\ge \epsilon}. The {1}-convexity of {f_A^2} implies that

\displaystyle  f_A(c(B))^2 \ge f_A(c(A))^2+|c(A)-c(B)|^2 \ge r(A)^2 + \epsilon^2

On the other hand, since {|f_A-f_B|\le d_{\mathcal H}(A,B)} everywhere,

\displaystyle  f_A(c(B))\le f_B(c(B)) + d_{\mathcal H}(A,B) = r(B) + d_{\mathcal H}(A,B) \le r(A) + 2 d_{\mathcal H}(A,B)

Putting things together,

\displaystyle  d_{\mathcal H}(A,B) \ge \frac12 (\sqrt{r(A)^2 + \epsilon^2} - r(A))  = \frac{\epsilon^2}{2( \sqrt{r(A)^2 + \epsilon^2} + r(A) )}

Thus, as long as {r(A)} remains bounded above, we have an inequality of the form {d_{\mathcal H}(A,B) \ge c\, \epsilon^2}, which is exactly {1/2}-Hölder continuity.

Remark. The proof uses no information about {\mathbb R^n} other than the {1}-convexity of the squared distance function. As such, it applies to every CAT(0) space.

2 thoughts on “Continuity of circumcenter and circumradius”

  1. This is nice, thank you. I would have avoided calling it “circumcentre” since it is distinct from the traditional usage of that term, in obtuse triangles for example.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s