A geometric ordering problem

Question

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?

Answer 1

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$.

Answer 2

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.