0
$\begingroup$

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|$?
$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the excellent answer! :) $\endgroup$
    – shamisen
    Commented Dec 29, 2014 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .