# Comparison of the Chebyshev centers and radii of a set and of its bounding box

The Chebyshev center of a bounded set $Q$ having non-empty interior is defined in this question as the center of the minimal-radius ball enclosing the entire set $Q$.

Let $B$ be the minimum-volume axis-aligned box containing the set $Q$, $r_B$ the radius of the minimal-radius ball enclosing $B$ and $r_Q$ the radius of the minimal-radius ball enclosing $Q$.

My questions are the following:

1. It is true that the Chebyshev center of $Q$ is always inside $B$?
2. Given that (1) is true, is there any upper bound to $|r_B - r_Q|$?

## 1 Answer

1) is true. The reason is that the Chebyshev center $c$ of $Q$ is contained in its closed convex hull $K$ (the intersection of all closed halfspaces containing $Q$). Every closed convex set containing $Q$ also contains its closed convex hull.

To justify $c\in K$, suppose this fails: then there is a hyperplane separating $c$ from $K$. Moving $c$ toward $K$ along the normal to this hyperplane brings $c$ strictly closer to every point of $K$ (by the Pythagorean theorem). This contradicts $c$ being the Chebyshev center of $Q$.

2) Any upper bound on $|r_B-r_Q|$ would have to scale with the size of the set, so it can't be universal. It is better to estimate $r_B/r_Q$, which is unitless. Of course, $r_Q\le r_B$ since $Q\subset B$. On the other hand, $B$ is contained in the cube circumscribed around any ball containing $Q$, which implies $r_B\le \sqrt{n}r_Q$. And this bound is optimal, because it's attained when $Q$ is a ball.

• Thanks for the excellent answer! :) Dec 29, 2014 at 13:20