Subsets of a set of points that can lie in the same sphere

Question

Suppose I have a finite set $\mathcal{P} := \{x_1, x_2, \ldots , x_n\} \subset \mathbb{R}^d$.

Is there any way to characterize the couples $(x_i, x_j)$ such that there exists a ball $B$ with $x_i, x_j \in B$ but all the other points in $\mathcal{P}$ are not inside $B$.

Some obvious remarks on the question :

$\bullet$ For any point $x_i$, take the point $x_j$ that is closest to $x_i$, then $(x_i, x_j)$ verifies the desired property.

$\bullet$ For a couple $(x_i, x_j)$, if there exists an $x_k$ on the segment joining the two points, then $(x_i, x_j)$ cannot verify the property.

$\bullet$ It also seems that the edges between "adjacent extremal points of the convex hull'' (I don't know how to call these) always satisfy the property, as we may take a sphere with a centre far away.

This shows that this property is not really trivial. I have made a small approximate figure in the plane here, with the green edges representing the edges satisfying my problem (I only have an online drawing tool available :) ):

I am really looking for any necessary and/or sufficient condition, or reference if this has a name. Of course a partial answer on the plane would be nice already.

My further objective is to get a necessary and sufficient condition for the same property but for more than two points, and to impose that the center of the sphere lies outside the convex hull of the points.

Answer 1

Assuming closed balls are allowed, $(x_i, x_j)$ have the property if there is $x$ such that $x_i$ and $x_j$ are the two closest points to $x$ in your set, i.e. $\max(|x-x_i|, |x-x_j|) < |x-x_k|$ for all $k \notin \{i,j\}$. Note that if $x$ works here, so does any point in some neighbourhood of $x$. Thus for simplicity we can restrict our attention to the points whose distances to all the $x_j$ are distinct, i.e. the complement $U$ of the union of hyperplanes $P_{ij} = \{x: |x - x_i|=|x-x_j|\}$, $1 \le i < j \le n$. These hyperplanes divide $U$ into domains, in each of which the points $x_i$, $x_j$ are placed in a fixed order by their distances to a point in the domain. $(x_i, x_j)$ have the property if at least one of these domains has $x_i$ and $x_j$ as the first two in that order.

Answer 2

I'll assume we're working in $\mathbb{R}^2,$ though I think the idea works in $\mathbb{R}^n$ with modifications.

If $(x_i,x_j)$ verifies the property for a ball $B,$ then if $B$ can be replaced by another ball $B'$ where $B' \subseteq B,$ $(x_i,x_j)$ will also verify the property for the ball $B'.$ This means we may assume that each of $x_i,x_j$ lies on the bounding circle of $B.$ For if initially both are interior to $B$ we may decrease the radius of $B$ keeping its center fixed until the furthest from center of $x_i,x_j$ (say $x_i$) lies on the bounding circle, and then if $x_j$ is still in the interior we may move the center of $B$ along the segment joining its center at that stage to the boundary point $x_i$ while keeping the bounding circle of $B$ passing through $x_i$, until such time as $x_j$ also lies on the bounding circle. In both changes of $B$ it has moved to subsets of itself.

Now consider any third point $x_k$ in the given set of points. If it happens that $x_k$ lies interior to the segment joining $x_i,x_j$ then $(x_i,x_j)$ does not verify the property (as noted by the OP). Secondly if $x_k$ happens to lie elsewhere on the line through $x_i,x_j$ then this $x_k$ will be outside the ball $B$ so has no effect on the question whether $(x_i,x_j)$ verifies the property.

Needed adjustment: In case the circle bounding ball $B$ through $x_i,x_j,x_k$ has all other points strictly outside it, then that $B$ does not verify the property for the pair $(x_i,x_j).$ However since all other points are at strictly positive distance from $B,$ the bsall $B$ may be adjusted slightly so as to have $x_i,x_j$ on its bounding circle but hsve $x_k$ and all remaining points strictly outside it.

Now the rest is a tedious computation which will end up deciding one way or the other if the pair $(x_i,x_j)$ verifies the property. For each fixed $x_k$ (not on the line through $x_i,x_j$) we form the circle through $x_i,x_j,x_k$ and check whether all the remaining points in our given finite set happen to lie outside that circle. If any of these $x_k$ give all the remaining points outside its circle we can stop, and say that $(x_i,x_j)$ verifies the property. However if none of the $x_k$ tested has all remaining points outside the generated circle, we can say that $(x_i,x_j)$ does not verify the property.

I may need to elaborate on why the failure of all tested $x_k$ proves the pair $(x_i,x_j)$ does not verify the property. (Will return to this later if I can word that argument well.)