3
$\begingroup$

This is not homework, and I don't even know if this is possible, but I'm curious:

Given a list of points in Euclidean space, is it possible to find the center of a sphere that encompasses all of the points? These points would either lie inside the sphere or on the surface. Ideally one wouldn't have to compare the distances of each endpoint from all the other endpoints, but if that's the only way then that's the only way.

Update

Looking for the smallest radius sphere that encompasses a finite number of points.

$\endgroup$
11
  • $\begingroup$ If you are given only finitely many points, then a sphere of sufficiently large radius at any center will be able to contain all the given points... Likewise, if given infinitely many points, then depending on whether the points form a bounded set or not, either any center will exhibit such a sphere or there is no such sphere. ...Or are you asking whether there is an algorithm to determine if a set of points is bounded? $\endgroup$ – suncup224 Aug 23 '14 at 12:43
  • $\begingroup$ Or maybe I understood the word "endpoints" wrongly. Are these points hypothesized to be points on the surface of a sphere? $\endgroup$ – suncup224 Aug 23 '14 at 12:49
  • $\begingroup$ @suncup224 I might be using the wrong terminology. The 'endpoints' could be either inside of a sphere or on the surface of the sphere. You are right about a sufficiently large radius sphere, although I'm looking for the sphere with the smallest radius that encompasses the points. This would definitely be a finite number of points. $\endgroup$ – MDMoore313 Aug 23 '14 at 13:15
  • 1
    $\begingroup$ Here is a succinct statement of what you want: Given a set of points $x_i\in \mathbb{R^n}$, what is $\displaystyle \min_{x\in\mathbb{R}^n}\;(\max_{x_i\in S}|x-x_i|)$ and for what $x$ does this occur? $\endgroup$ – Semiclassical Aug 23 '14 at 14:02
  • 1
    $\begingroup$ Just realized that Wikipedia has an entire article on this: en.wikipedia.org/wiki/Bounding_sphere. It includes some reference to literature and a discussion of known algorithms. $\endgroup$ – Semiclassical Aug 23 '14 at 14:08
0
$\begingroup$

First, solve the problem for the circle. If we have a set of randomly distributed but clustered points, at least two of them will be on the circumference of a circle that encompasses all of the points. An algorithm to find those two points could work in the following way. Form a set of all of the combinations of two members of the point set. For each pair plot two circles: one bulging one way, the other the other way. For each circle check if any point is outside, when there are none we have found the desired circle. The algorithm for the sphere is a simple extension of that for the circle.

NB I'm not claiming this is efficient for large point sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.