1
$\begingroup$

suppose that $x_0 , x_1 , . . . , x_k \in R^k$, I want to show that the set of all points that are closer to $x_0$ than other $x_i$ (in Euclidean norm), is a polyhedron. This is my Books solution:

$|| x-x_0|| \leq ||x-x_i|| \iff (x-x_0)^T(x-x_0) \leq (x-x_i)^T (x-x_i) \iff x^T x-2x_0x + x_0^Tx_0 \leq x_T x - 2x_i^Tx+x_i^T x_i \iff 2(x_i - x_0)^T x \leq x_i^T x_i - x_0^Tx_0$ That defines a halfspace.

I dont understand the last part, How the last term represent's a halfspace?(perhaps I did not understand the meaning of polyhedron and halfspace right)

Are there any alternative solutions for this problem?

$\endgroup$

2 Answers 2

2
$\begingroup$

A halfspace in $\mathbf R^k$ is what lies on one side of a hyperplane. Hyperplanes can be described as level sets of linear functionals, $f \colon \def\R{\mathbf R}\R^k \to \R, x \mapsto b^t x$ (for some $b \in \R^k$), that is, for every $a \in \R$, $$ H := \{x \in \R^k : f(x) = a \} = \{x \in \R^k : b^t x = a \} $$ is a hyperplane (think of $k = 2$, where hyperplanes are lines). The spaces of both sides of $H$ are described by the fact, that $f$ is at most (or at least) equal to $a$ there, hence a halfspace is always of the form $$ \{x \in \R^k : b^t x \le a \} $$ (or $\{x \in \R^k : b^t x \ge a \}$, but we can replace $b$ by $-b$ then). Your case is the same, but with "fancy" $a \in \R$ and $b \in \R^k$. They are made from the given data, we have $$ b = (x_i - x_0) \in \R^k, \quad a = x_i^t x_i - x_0^t x_0 \in \R$$ So your equation describes a hyperplane.

As a polyhedron is by the very definition the intersection of halfspaces, I do not see a way how the use of halfspaces can be avoided in the argument.

$\endgroup$
1
$\begingroup$

Maybe it will be clearer if we use the notation for an inner product. Considering vectors in $\mathbb{R}^k$ as column vectors, let $\left< v, w \right> = v^T w$. Then, for some fixed non-zero vector $w_0 \in \mathbb{R}^k$, the equation $\left< v, w_0 \right> = 0$ defines a hyperplane passing through the origin for which $w_0$ is the normal vector. The equation $\left< v, w_0 \right> = c$ defines a hyperplane that does not necessarily pass through the origin (with the same normal). The inequality $\left< v, w_0 \right> \leq c$ defines a half-space whose boundary is the hyperplane $\left< v, w_0 \right> = c$.

$\endgroup$

You must log in to answer this question.

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