Find a point such that the maximum distance to any point in the set of points P is minimized

Question

Given the set of points in the 2d-space P, where Pi = (Xi, Yi),

I need to find the target point T, so that the maximum distance to any Pi is minimized.

T must not exist in P and can be arbitrarily defined

Is there an algorithm I can use for this?

+5

jdeuce May 24, '12 at 14:56

3 answers

Ants aasma · Answer 1 · 2012-05-24T15:03:50+0000

Karusmeister · Answer 2 · 2012-05-24T15:29:33+0000

Think this may be the solution to your problem with a pretty good explanation, but this is O (n ^ 2)

jdeuce · Answer 3 · 2012-05-25T19:57:26+0000

, , :

(min (Xi) + max (Xi))/2, (min (Yi) + max (Yi))/2)