3

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.

MDMoore313
  • 131
  • 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? – suncup224 Aug 23 '14 at 12:43
  • Or maybe I understood the word "endpoints" wrongly. Are these points hypothesized to be points on the surface of a sphere? – suncup224 Aug 23 '14 at 12:49
  • @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. – MDMoore313 Aug 23 '14 at 13:15
  • Couldn't you average the co-ordinates of all the points to find the centre and then the radius would be from that point to the most extreme point ? – dilbert Aug 23 '14 at 13:22
  • May be : are you asking for the smallest sphere ? – Claude Leibovici Aug 23 '14 at 14:01
  • @ClaudeLeibovici yes – MDMoore313 Aug 23 '14 at 14:01
  • 1
    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? – Semiclassical Aug 23 '14 at 14:02
  • @Dilbert I don't know, Could I?? What would the formula be for that, some type of summation? I'd like to not have to iterate over the set n^n times, if possible. – MDMoore313 Aug 23 '14 at 14:03
  • 1
    Just realized that Wikipedia has an entire article on this: http://en.wikipedia.org/wiki/Bounding_sphere. It includes some reference to literature and a discussion of known algorithms. – Semiclassical Aug 23 '14 at 14:08
  • @SemiClassical, thnx , I didn't Google that term, didn't know what to call it – MDMoore313 Aug 23 '14 at 14:13
  • I didn't either, I just stumbled upon it while searching "smallest sphere containing points." The upshot seems to be that it's a well-studied problem, and one for which there are known effective algorithms (the animation on that Wikipedia page is a nice depiction of one.) – Semiclassical Aug 23 '14 at 14:17

1 Answers1

0

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.