Let $x_0,x_1,...,x_k\in R^n$. Consider a set $V_i:=\{x\in R^n:\|x-x_i\|_p\leq\|x-x_j\|_p \mbox{, } \forall i\neq j\}$
For $p=2$, show that $V_i$ is a polyhedral set.
Generate $10$ points randomly in $R^2$, which are well spread from each other. Take $p=2$ and plot $V_i$ for each $i=1,...,10$.
Construct an algorithm to find $A\in R^{m\times n}$ and $b\in R^n$ such that $V_i = \{x\in R^n: Ax\leq b\}$. Justify each step of the algorithm rigorously.
For the first part, I tried this: $$\|x-x_i\|_2\leq\|x-x_j\|_2 \implies (x-x_i)^T(x-x_i) \leq (x-x_j)^T(x-x_j)$$ $$\implies x^Tx-2x_i^Tx+x_i^Tx_i \leq x^Tx-2x_j^Tx+x_j^Tx_j$$ $$\implies 2(x_j-x_i)^Tx \leq x_j^Tx_j-x_i^Tx_i$$
which is enough to define a half space and hence, a polyhedron I think. Is this proof correct? My main issue starts with the next parts of this question. I have been asked to plot these sets in Matlab and I have no idea how to do it. I know about plotting Voronoi diagrams in Matlab, but this involves the decompositions of the Voronoi sets and I am not sure how to proceed. Secondly, can someone give an insight of what this set represents? Maybe that will help me a bit. Finally, I have no idea on how to go about the third part. All hints are appreciated.
Thanks
The set $V_i$ consists of the points closer to $x_i$ than to any other $x_j$.
To plot $V_i$, for each $j$ you can plot the set of points that is separated as far from $x_i$ as from $x_j$ (equidistant). That set is a line. After doing that for each $j$, some of those lines will be the boundary of $V_i$. Let $x_i, x_j \in \mathbb{R}^2$. Let's find two points that are equidistant. The midpoint $(x_i+x_j)/2$ is equidistant. Another point can be found using the observation that the line is perpendicular to the line through $x_i$ and $x_j$; so is $(x_i+x_j)/2 + v$ where $v$ is a nontrivial solution to $v^T(x_i-x_j) = 0$. After you find such $v$, you can draw the line with Matlab's line function (and then repeat for the other $j$ to finish $V_i$).
You have shown that: $$V_i = \left\{ x \in \mathbb{R}^n : 2(x_j-x_i)^Tx \leq x_j^Tx_j-x_i^Tx_i \forall i \neq j\right\}$$ So for part 3, you can create the matrix $A \in \mathbb{R}^{(n-1)\times n}$ with $2(x_j-x_i)^T$ as rows (one row for each $j$), and $b \in \mathbb{R}^{n-1}$ with elements $x_j^Tx_j-x_i^Tx_i$ (one element for each $j$).