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
    Commented 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
    Commented May 16, 2013 at 2:02

You must log in to answer this question.

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