Find the point with minimum max distance to any point in a set Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?
This is the smallest enclosing circle problem, and can be solved in linear time. Also, these slides describe a randomized algorithm that runs in expected linear time.