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
    Dec 29, 2014 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.