0
$\begingroup$

I am trying to show the above statement:

Show that the set of points that are nearer $a$ than $b$ in the sense of Euclidean $\lVert\cdot\rVert_2$ are convex.

My attempt

This follows from the Proposition: The convex hull of $M \subset \mathbf R^2$ is convex, indeed the smallest convex set that contains $M$. Moreover, co($M$) is the set of all convex combinations of points of $M$,

\begin{equation} \text{co}(M) := \{x \in \mathbf R^2 | \exists x_1, x_2, ... , x_N \in M \text{ such that } x = \sum\limits_{i=1}^{N} \lambda_i x_i,\\ \text{ for some } \lambda_1, \lambda_2, ..., \lambda_N, \text{ where } \lambda_1 \geq 0 \forall i, \sum\limits_{i=1}^{N} \lambda_i = 1 \}. \end{equation}

The main idea is based on the idea about the corollary 1.14 in http://www.math.udel.edu/~angell/ch1.pdf:

The convex hull of a compact set in $\mathbf R^n$ is compact.

Assume $C \subset \mathbf R^n$ be compact. See the original source for the skipped steps. The sequence $\{A\}_{k=1}^{\infty}$ has a subsequence $\{AA\}_{j=1}^{\infty}$ which converges to a point of co $(C)$ which shows that this latter set is compact.

If $C$ is closed and convex, it has a smallest/nearest element in a certain sense. It is a simple result for analysis that involves the fact that the function $x \to \lVert x\rVert$ is a continuous map from $\mathbf R^n \to \mathbf R$ and the fact that Cauchy sequences in $\mathbf R^n$ converges.

We need also the theorem: Every closed convex subset of $\mathbf R^n$ has a unique element of minimum norm. See the proof in the source above.

There must be also a simpler way to prove the statement. Is there any sense in my attempt? How can you show the statement?

$\endgroup$
1
$\begingroup$

The set is a hyperplane. I think you are over-thinking the problem.

The set in question is $$ \left||a-x\right|| \lt \left ||b-x\right|| \Leftrightarrow\left||a-x\right||^2 \lt \left ||b-x\right||^2$$ Writing out the norms we get $$ (a\cdot a) - 2 (a \cdot x) + (x \cdot x) < (b\cdot b) - 2 (b \cdot x) + (x \cdot x)$$ Cancelling $(x \cdot x)$ and rearranging $$ (c \cdot x) < (b\cdot b) - (a\cdot a) ~\text{ where $c = 2(b-a)$}$$

Let us write the above inequality as $$(c \cdot x) < d$$

This is clearly a convex set: If $x$ and $y$ are in the set then $$ (c \cdot (\lambda x + (1-\lambda) y ) = \lambda (c \cdot x) + (1-\lambda) (c \cdot y)< \lambda d + (1-\lambda) d = d $$

$\endgroup$
1
  • $\begingroup$ Not a hyperplane, but a halfspace. $\endgroup$ Feb 6 '14 at 3:01
1
$\begingroup$

Let $\phi(x) = \|x-a\|^2-\|x-b\|^2= \|a\|^2-\|b\|^2+2 \langle b-a, x \rangle$. $\phi$ is affine (that is, linear plus a constant) hence convex, and so $\{ x | \phi(x) < 0\}$ is convex.

Note: Since it also follows from the above that $\{ x | \phi(x) > 0\}$ is convex, we see that the sets are open half-spaces separated by the hyperplane $\{ x | \phi(x) = 0\}$.

$\endgroup$
2
  • $\begingroup$ What do you mean by this $\{x|\Phi(x) < 0\}$? $\endgroup$ Jan 19 '14 at 13:10
  • 1
    $\begingroup$ It means the set of $x$ that satisfy the inequality $\phi(x) <0$, where $\phi$ is the function defined on the first line. $\endgroup$
    – copper.hat
    Jan 19 '14 at 17:07

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.