Finding the smallest hypersphere with $\leq d+1$ boundary points in $\mathbb{R}^d$?

Given a set of points $X \subseteq \mathbb{R}^d$, where $2\leq|X|\leq d+1$, how would one go about computing the center and radius of the $(d-1)$ sphere with the smallest radius where these points in $X$ lie?

For 2 points, $\vec{x}_0$ and $\vec{x}_1$, we find the midpoint $\frac{\vec{x}_0+\vec{x}_1}{2}$, which is the center point, and the radius $r = \frac{\|\vec{x}_0 - \vec{x}_1\|_2}{2}$

So, for any $3\leq k+1\leq d+1$ points, would the center of this hypersphere always be the centroid: $$\overline{X} = \frac{1}{k+1}\sum_{i=0}^{k} \vec{x}_i$$ with a radius being the Euclidean distance from the centroid to any point in $X$? How would I prove that all of these points are equidistant from the centroid? Or is am I thinking about this wrong? I think I'm wrong...

Let's say we have three points $(1,0),(-1,0),(0,1)$, and the center would be $(0,\frac{1}{3})$ with distances $\sqrt{1 + \frac{1}{9}} = \frac{\sqrt{5}}{3}$, $\sqrt{1 + \frac{1}{9}} = \frac{\sqrt{5}}{3}$, and $\sqrt{0 + \frac{4}{9}} \neq \frac{\sqrt{5}}{3}$, so I'm no longer sure about my reasoning.

• Ahh yes! Thank you, totally forgot to include this – Brad Flynn Feb 18 '17 at 2:21

Given three points A,B,C in the plane, not collinear, the circle you want has its center where the perpendicular bisectors of the three triangle edges meet. Call that point P.

Next, take those three points ABC, circle center P, but now add a fourth point D off the original plane. Every sphere with the three original points on boundary contains the circle we made. It follows that the center of the sphere we want lies along a line through P but perpendicular to the plane containing ABC. Then take three different points, maybe ABD, in that plane find circle center Q, draw a line through Q perpendicular to ABD. These two lines will meet in the center of the sphere we want.

Sphere-sphere intersection is not a surface

For dimension four, keep going.

• Why is it that the perpendicular bisector meets at the center of this circle? And the center of the sphere is along that line perpendicular to the original enclosed triangle? – Brad Flynn Feb 18 '17 at 3:43
• Is this because the circumcenter make an isosceles triangle with each edge combination? So this operation will always take time linear to $k+1$ computations? – Brad Flynn Feb 18 '17 at 16:42
• And for the fourth dimension, we have this point of intersection between P and Q that was the center of a 2-sphere, what is the "perpendicular" to that point? Is it a plane? And now we have a fifth point E, does this "perpendicular" of the faces ABCE and ABDE meet at a single common point? Sorry, just a little confused on how to construct this. – Brad Flynn Feb 18 '17 at 17:18
• @BradFlynn, really encourage you to deal with the two and three dimensional problems first, especially calculating a few examples each, also making some good drawings. You are right about the isosceles triangles. Next, the intersection of two spheres in R^3 is a circle (if they intersect in more than a point); the line joining the centers of the spheres is perpendicular to the plane of that circle, and intersects that plane in the center of that circle; here, we are forcing that circle to be the original ABC circle, center I called P. – Will Jagy Feb 18 '17 at 17:25
• How does one find the circle from the intersection of spheres, and how many operations go into that? I'm getting the feeling that this is taking an overall time quadratic to the number of points? – Brad Flynn Feb 18 '17 at 17:35