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.

Four-point CAT(0) condition

The definition of a metric space guarantees that if we pick three points {A,B,C} from it, we can draw a triangle in the Euclidean plane, with vertices labeled {A,B,C} so that the side lengths are equal to the corresponding distances {|AB|, |BC|, |CA|} in the metric space. In other words, we can represent any triple of points as vertices of a triangle.

Triangle representation
Triangle representation

The above paragraph is from Tight spans and Gromov hyperbolicity, but here the similarity ends. Moving on to four points {A,B,C,D} we find that it is possible to draw a quadrilateral with side lengths equal to the corresponding distances
{|AB|, |BC|, |CD|, |DA|}.

Quadrilateral with prescribed side lengths
Quadrilateral with prescribed side lengths

Except for the degenerate case (one length equal to the sum of three others), the quadrilateral is not rigid: one can change the angles while keeping the sidelengths the same.

Since the quadrilateral has one degree of freedom, we cannot hope to have the correct lengths of both diagonals {AC} and {BD}. One of two diagonals can be made to match the metric space distance, just be drawing two triangles and gluing them together. But this is not so interesting.

There is an interesting class of metric spaces for which one can always draw a Euclidean quadrilateral as above so that neither diagonal is too short (they are allowed to be too long). These are called CAT(0) spaces, and they generalize the concept of a Riemannian manifold of nonpositive sectional curvature (more on this later). Every Euclidean space is CAT(0) for obvious reasons.

For example, if a CAT(0) space contains four points with pairwise distances {|AB|=|CD|=2}, {|BC|=|DA|=1}, then {|AC|^2+|BD|^2\le 10}. Indeed, any Euclidean quadrilateral with these sidelengths is a parallelogram, in which the sum of squares of the diagonals is {2\cdot (2^2+1^2)=10}. (It never pays to draw {ABCD} with self-intersections, because that only makes the “diagonals” shorter).

For a non-parallelogram example, take {|AB|=2}, {|BC|=3}, {|CD|=4},and {|DA|=5}. The diagonal lengths {|AC|=4} and {|BD|=6} are allowed by the axioms of a metric space, but not by the CAT(0) condition.

Non-CAT(0) quadrilateral
Non-CAT(0) quadrilateral

This can be checked using a bunch of cosine formulas:

\displaystyle    \cos\angle ADB = \frac{5^2+6^2-2^2}{2\cdot 5\cdot 6} =\frac{19}{20}, \\ {}\\    \cos\angle CDB = \frac{4^2+6^2-3^2}{2\cdot 4\cdot 6} =\frac{43}{48}, \\ {} \\   \cos\angle CDA = \frac{|AD|/2}{|CD|} =\frac{5}{8},

where the last computation is simpler because {\triangle CDA} is isosceles. Since {\angle CDA=\angle CDB+\angle ADB}, the addition law of cosines yields a contradiction.

Let’s see what CAT(0) has to do with curvature. First, a closed curve with intrinsic metric is not a CAT(0) space. Indeed, one can find four points {A,B,C,D} on the curve that are equally spaced at distances {L/4}, where {L} is the length of the curve. Then the corresponding Euclidean quadrilateral must be a rhombus of sidelength {L/4}. One of its diagonals will be at most {L\sqrt{2}/4}, which is less than {L/2} required by the intrinsic metric of the curve.

As a corollary, a CAT(0) space does not have closed geodesics. One can object that compact negatively curved manifolds (e.g., double torus) have plenty of closed geodesics. The answer is that to actually characterize nonnegatively curved spaces, one must impose the CAT(0) condition only locally.

The standard definitions of a CAT(0) space require any two points to be connected by a geodesic, and are stated in terms of geodesics. Here is one of them: for any geodesic {\gamma\colon [a,b]\rightarrow X} and for any fixed point {A\in X} the function

\displaystyle  F(t)=d\,^2(\gamma(t),A)-t^2 \ \ \ \ \ (1)

is convex. (Here {d\,^2} is the square of the distance.)

Distance function on a geodesic
Distance function on a geodesic

The condition (1) may look contrived, until one realizes that in a Euclidean space {F} is always an affine function. Thus, the definition says that the distance function in a CAT(0) space is at least as convex as in a Euclidean space. By the way, (1) indeed implies that {t\mapsto d(\gamma(t),A)} is a convex function. I leave this as an exercise.