1
$\begingroup$

Let $C$ and $D$ be two convex sets. And suppose $C\cap D\neq \emptyset$. Let $x^*$ is the solution to the optimization problem:

$$\min_{x\in C} \max_{y \in D} |x-y|^2$$

Is it true that $x^* \in D$. Without the constraint $x\in C$ this is the minimum enclosing ball problem and the statement is true. I am almost positive this should be true too but can't seem to find a proof.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I don't think it is true, even if you restrict C and D to be in a class of (pairs of) congruent triangles. It might become true if you place bounds on the eccentricity of the shapes permitted. Gerhard "Ask Me About System Design" Paseman, 2013.05.15 $\endgroup$
    – Gerhard Paseman
    May 15, 2013 at 23:59

1 Answer 1

Reset to default
1
$\begingroup$

It's not true. Consider when $C$ and $D$ are two long skinny rectangles, at a slight angle to each other, and only overlapping at one end, so that $C \cup D$ looks like a tall skinny $V$. Then $y$ is at the corner of $D$ furthest from the base of the $V$, and $x^*$ is on the other arm of the $V$, near but not quite at the top.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ x* is near the middle of C, not at the top. For more examples, pick a domain D which is sufficiently eccentric, and consider the level sets of x such max(x,y) is some constant m as y ranges over D. One can then find C intersecting D and also a "least" level set with points outside of D. Gerhard "Ask Me About System Design" Paseman, 2013.05.15 $\endgroup$
    – Gerhard Paseman
    May 16, 2013 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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