Consider m data points in n dimensional data space, and we want to fit a minimal hyper sphere, which covers all these data points .
to find center and radius of such minimal hyper sphere is NP task. I am interested in efficient algorithms, which may be either exact algorithm or approximation algorithm or randomized algorithm.
Dear Sanjay Garg ,
Could you explain your claim ( the task is NP )?
I think the answer is in P, based on the given data
and the dimension of the space.
For example, if n = 2 and m > 3, then
the problem ( if we exclude the special cases) is not solvable.
Are there any relation on m, and n?
For example, m is less than or equal n +1,
and the m points are not collinear.
Best regards
The following project and its article is related to this problem. The technique described in the article is not presented as an algorithm, but it could give you ideas to solve the mentioned problem.
https://www.researchgate.net/project/A-Theory-of-Networks-K-geodetic-Networks-applied-to-the-Solution-of-Problems-in-Another-Type-of-Networks-Complex-Networks
Could the center of mass of a system of points be the center of the sphere, and the most distant point from the center determine the radius?
- Badges
- Science topic