A geometric ordering problem The following problem occurred to me the other day.
Given two distinct real numbers $x_1$ and $x_2$ (let's call them points in $\mathbb{R}$). Trivially, I can always find a third point that it's either closer to $x_1$ than to $x_2$ or vice-versa. In other words, I can always solve either
$$
|p-x_1|<|p-x_2|\,\,\,\text{ or }\,\,\,|p-x_2|<|p-x_1|
$$
for some $p\in\mathbb{R}$.
Extending this thought to $\mathbb{R}^2$ and considering three non-collinear points $x_1,x_2$ and $x_3$, can I always solve
$$
|p-x_i|<|p-x_j|<|p-x_k|
$$
for any permutation of $i,j,k$, where $i,j,k\in\{1,2,3 \}$ and $i\neq j\neq k$. That is, ordering $x_1,x_2$ and $x_3$ in any of the $6$ possible ways, can I always find a point which is closest to the first point, second closest to the second and so on?
It might slightly boring to prove, but I believe the answer to be yes, where non-collinearity is trivially needed. For example,

I wonder, however, how to argue when extending this problem to $\mathbb{R}^n$. That is, given $n+1$ points not lying in the same hyperplane, can I always find a point $p\in\mathbb{R}^n$ such that
$$
|p-x_{i_1}|<|p-x_{i_2}|<\cdots <|p-x_{i_{n+1}}|
$$
for any permutation of indexes $\{i_k\}_{1\leq k\leq n+1}$? If the answer is positive, and if there are infinitely many solutions, what kind of set is the solution set?
 A: Go back to the $\Bbb R^2$ case first: Consider the lines $L_{12}, L_{13}, L_{23}$ perpendicular to and passing through the midpoints of the line segments $\overline {x_1x_2}, \overline{x_1x_3}, \overline{x_2x_3}$ respectively. Each of these lines divides the plane in two. All points on the $x_1$ side of $L_{12}$ are closer to $x_1$ than $x_2$, and all points on the $x_2$ are closer to $x_2$ than $x_1$.
If the three lines intersected in a triangle, then for a point $p$ inside the triangle for an appropriate relabeling $x_1, x_2, x_3$, you would find that $px_1 < px_2, px_2 < px_3, px_3 < px_1$ would hold, requiring that the distance from $p$ to $x_1$ be strictly less than itself. Hence, it must be that $L_{12}, L_{13}, L_{23}$ intersect in a single point $C$. This is the well-known result that given any three non-colinear points, one can always find a circle that passes through them.
The three lines therefore break the plane into six wedge-shaped regions having $C$ as their apex. In each of these regions the distances of points to $x_1, x_2, x_3$ is ordered per one of the six arrangements of those points, thus showing that indeed, all arrangments are possible.
For higher dimensions, instead of the $L_{ij}$ being lines, they are hyper-planes of codimension $1$. But given $n+1$ points in general position in $n$-dimensional space, there is always a point that is equidistant from all of them, so once again, all the $L_{ij}$ must intersect in that point, dividing $\Bbb R^n$ into conic regions where the distances to each of the $x_i$ are ordered per one of the orderings on the $x_i$.
A: If the $n+1$ points are not lying on a hyperplane, we can solve the linear system of equations
$$
\begin{pmatrix}
\phantom{0} & x_1^T & \phantom{0} & 1 \\
\phantom{0} & x_2^T & \phantom{0} & 1 \\
\phantom{0} & \vdots & \phantom{0} & \vdots \\
\phantom{0} & x_{n+1}^T & \phantom{0} & 1
\end{pmatrix}
\begin{pmatrix}
\phantom{0} \\
p \\
\phantom{0} \\
c
\end{pmatrix}
= 
\begin{pmatrix}
\frac12 (x_1^Tx_1 - a_1) \\
\frac12 (x_2^Tx_2 - a_2) \\
\vdots \\
\frac12 (x_{n+1}^Tx_{n+1} - a_{n+1})
\end{pmatrix}
$$
The condition "The points are not lying on a hyperplane" means that the matrix on the left side is invertible.
Once we solved this equation, we have
$$
x_i^Tp + c = \frac12 (x_i^Tx_i - a_i)
$$
or
$$
p^Tp - 2x_i^Tp + x_i^Tx_i = a_i + p^Tp + 2c
$$
or
$$
(p-x_i)^T(p-x_i) = a_i + p^Tp + 2c
$$
which means that I can adjust the differences of the squares of the distances $\|p-x_i\|$ however I like, by means of the $a_i$.
Example:
If I want $\|p-x_2\| < \|p-x_3\| < \|p-x_1\|$, I can simply set $a_2 = 0,$ $a_3 = 1$ and $a_1 = 2,$ calculate $p$ as shown above and I will get
$$
\|p-x_2\| = \sqrt{r + 0} \\
\|p-x_3\| = \sqrt{r + 1} \\
\|p-x_1\| = \sqrt{r + 2}
$$
with a suitable $r$.
Regarding the kind of set of the solution set: If we set
$$
B = \begin{pmatrix}
1 &   & & 0 & 0 \\
  & 1 & &   & 0 \\
  & & \ddots & & \vdots \\
0 & &        & 1 & 0
\end{pmatrix}
\begin{pmatrix}
\phantom{0} & x_1^T & \phantom{0} & 1 \\
\phantom{0} & x_2^T & \phantom{0} & 1 \\
\phantom{0} & \vdots & \phantom{0} & \vdots \\
\phantom{0} & x_{n+1}^T & \phantom{0} & 1
\end{pmatrix}^{-1}
$$
and 
$$
M = B
\begin{pmatrix}
\frac12 x_1^Tx_1 \\
\frac12 x_2^Tx_2 \\
\vdots \\
\frac12 x_{n+1}^Tx_{n+1}
\end{pmatrix}
$$
($M$ is the circumcenter of the simplex with the vertices $x_1,\ldots,x_{n+1}$) then we get
$$ p-M = -Ba
$$
which means that the position of $p$ relatively to $M$ depends linearly on the components of $a$. As multiplication of $a$ with a positive number does not change the relative order of the components of $a$, we can conclude that, for each point $p=M+q,$ the point $M+\lambda q$ is also part of the solution that fulfills the same distance ordering. This means that the sets are actually cone-like, with their apexes at $M.$
If two choices of $a$ have the same relative order of their components, then this order will also be preserved for all of their convex combinations:
$$
a_i < a_j, \;\; a^{\star}_i < a^{\star}_j\;\;\Rightarrow
\lambda a_i+(1-\lambda) a_i^{\star}
<\lambda a_j+(1-\lambda) a_j^{\star}
\;\;,\;\;\lambda\in[0,1]
$$
As the convex combination of the $a$s maps directly to the convex combination of the corresponding $p$s, we now even know that the solution sets are convex cones.
