Convexity of $\{x\in \mathbb R^n: |x-a| \leq \theta|x-b|\}$

Question

For which values of $\theta \in \mathbb R$ is the set $$S = \{x\in \mathbb R^n: |x-a| \leq \theta|x-b|\}$$ convex?

It's very simple to show that $S$ is convex for $\theta \leq 0$.

Now suppose $\theta > 0$, and let $x,y \in S, t \in [0, 1]$.

Then $|tx+(1-t)y-a| = |tx-ta+ta+y-a-ty+ta-ta| =|tx-ta+y-a-ty+ta|\\ \leq|tx-ta|+|y-a|+|-ty+ta|=t|x-a|+|y-a|+t|y-a|\leq \theta(t|x-b|+(1+t)|y-b|)$

Now, we want to find for which values of theta, $\theta(t|x-b|+(1+t)|y-b|) \leq \theta|tx+(1-t)y-b|$

But theta cancels out, so this is either true for all positive theta or it's false for all positive theta.

I am unsure how to continue now.

I think we can look at a specific example, like $S_1 = \{x\in \mathbb R^n: |x-a|\leq|x-b|\}$.

How do we show this set is / isn't convex?

Answer 1

The answer is $0\le\theta \le 1$. The reason should be evident if you understand the geometric interpretation.

When $\theta < 0$, the set is empty (assuming $a \neq b$). It is usually not considered convex.

When $\theta = 0$, the set is $\{a\}$ and is convex.

When $\theta=1$, the set is a half plane with border bisecting the line segment between $a$ and $b$. The set is clearly convex.

We now focus on the case of $0 < \theta < 1.$

$$ \{x\in \mathbb R^n: |x-a| \leq \theta|x-b|\}$$ $$ \Leftrightarrow \{x\in \mathbb R^n: {(\vert x-a\vert)}^2 \leq \theta^2{(\vert x-b\vert)}^2\} $$ $$ \Leftrightarrow \{x\in \mathbb R^n: (1-\theta^2)x^Tx -2(a^T-\theta^2 b^T)x \le \theta^2b^Tb-a^Ta\} $$ $$ \Leftrightarrow \{x\in \mathbb R^n: x^Tx -2\frac{(a^T-\theta^2 b^T)}{(1-\theta^2)}x \le \frac{\theta^2b^Tb-a^Ta}{(1-\theta^2)}\} $$ $$ \Leftrightarrow \{x\in \mathbb R^n: {\left(x -\frac{(a-\theta^2 b)}{(1-\theta^2)}\right)}^T{\left(x -\frac{(a-\theta^2 b)}{(1-\theta^2)}\right)} \le \theta^2\frac{a^Ta + b^Tb-2a^Tb}{(1-\theta^2)^2}\} $$ $$ \Leftrightarrow \{x\in \mathbb R^n: {\left\vert x -\frac{a-\theta^2 b}{1-\theta^2} \right\vert}^2 \le {\left(\theta\frac{\vert a- b \vert}{1-\theta^2}\right)}^2\} $$ $$ \Leftrightarrow \{x\in \mathbb R^n: {\left\vert x -\frac{a-\theta^2 b}{1-\theta^2} \right\vert} \le \theta\frac{\vert a- b \vert}{1-\theta^2}\} $$

It is now obvious that the set is a n-dimensional ball. Hence it is convex.

When $\theta > 1$, following almost the same line of arguments of the above (with $\theta$ becoming $1/\theta$, and roles of $a$, $b$ swapped), we can show that its complement set is a n-dimensional ball. Hence the set of concern (complement of a n-dimensional ball) is NOT convex.

We have completed the proof that the answer is $0 \le \theta \le 1$.

Answer 2

Regarding your specific example. The set of points $|x-a| = |x-b|$ is the set of points that are equidistant from $a$ and $b$. It should be a hyperplane perpendicular to the line joining $ab$, passing through the midpoint $x_0=\frac{a+b}2$, i.e. if we set $n = \frac{b-a}2$, then we should see the equation $n\cdot (x-x_0)= 0 $. Since $a = x_0 - n$ and $b = x_0 + n$, \begin{align} 0 &= |x-a|^2 - |x-b|^2 = |x-x_0 + n|^2 - |x-x_0 - n|^2 \\\iff 0&= |x-x_0|^2 + |n|^2 + 2（x-x_0)\cdot n - \big[|x-x_0|^2 + |n|^2 - 2（x-x_0)\cdot n\big] \\\iff 0 &= （x-x_0)\cdot n\end{align} as predicted. Now, the inequality one way or the other will instead lead (by the same reasoning) to one of $0 \le （x-x_0)\cdot n$ or $0 \ge （x-x_0)\cdot n$. In either case, this is a convex set (it is one side of an affine-linear subspace).

For the general case $0\le \theta \neq 1$, I think the answer is either a ball or the complement of a ball, but this is slightly harder to see geometrically. I suggest the method of Xiaohai's answer.

---

after-comments update: So its not so bad afterall! In the case $0\le \theta \neq 1$, then the quadratic terms don't cancel and we're left with something where we can complete the square. First lets save some e-ink and define the translated variable $y$ by $y=x-b$, and choose $c$ such that $y-c=x-a$ (i.e. $c=a-b$). Then the inequality is

\begin{align}|y-c|^2 &\le \theta^2 |y|^2 \\ \iff (1-\theta^2) |y|^2 + |c|^2 - 2y\cdot c &\le 0 \\ \iff (1-\theta^2)\left [ |y|^2 - 2y\cdot \frac c{1-\theta^2}\right ] + |c|^2 &\le 0\\ \iff (1-\theta^2) \left| y - \frac{c}{1-\theta^2}\right|^2 - \frac{|c|^2}{1-\theta^2} + |c|^2 &\le 0 \\ \iff (1-\theta^2) \left| y - \frac{c}{1-\theta^2}\right|^2 &\le \frac{\theta^2 |c|^2}{1-\theta^2} \end{align} Now, in the case $0\le \theta<1$, we have $1-\theta^2>0$ so when you divide through, you get

$$0\le \theta<1\implies \left| y - \frac{c}{1-\theta^2}\right|^2 \le \frac{\theta^2 |c|^2}{(1-\theta^2)^2} $$ This is the interior of a ball centered at $y=\frac{c}{1-\theta^2}$ i.e. $x = a+\frac{a-b}{1-\theta^2}$, with radius $\frac{\theta |c|}{1-\theta^2}=\frac{\theta |b-a|}{1-\theta^2}$. But if $\theta > 1$, then $1-\theta < 0$ so the inequality flips: $$\theta>1\implies \left| y - \frac{c}{1-\theta^2}\right|^2 \ge \frac{\theta^2 |c|^2}{(1-\theta^2)^2}$$ this is the exterior of a ball, and so its not convex.

Thanks to Gabriel Romon and A.$\Gamma$ in comments for the sketch!!