Minimum distance?

Question

There are 100 points like (x1,y1)...(x2,y2). I need to find an arbitrary point (a,b) where the distance from (a,b) to all 100 points is minimum.

I need a formula or an iterative method in detail for n such points.

x coordinate y coordinate
0 2
2 4
5 6
5 10
7 15
10 15
12 10
12 6
15 4
20 2


I need to find a point such that it is minimum distance for all points.

Can you give an expression to find this point (a,b) ?

Hi Duke,

Can you give the complete explanation with that example. If you feel that the points are more , give with 4 points.

Is this can be applicable to large number of points i,e greater than 60,000 points.?

Answer 1

I suppose You mean the sum of all distances from (a, b) to all other points? This is a well known problem, the same question was asked some time ago, please follow the link below to read my answer, You'll find there a method You need:
http://answers.yahoo.com/question/index;_ylt=AsjapY4oDn_Fk1epVi5KulHty6IX;_ylv=3?qid=20071103182545AA1l69b&show=7#profile-info-d80dc8bc16566bd4b6363642fd3d9034aa

EDIT(after having read the additional details) The required point can be found by the procedure, described in my answer You have the link to above. The calculations are somewhat lengthy, I did them on my computer, first I checked whether one of the given points is the required one /condition (2)/, then, solving the system in condition (1) I found the following point with the approximate coordinates:
8.609; 7.879
Please follow the link below to see a picture:
http://i219.photobucket.com/albums/cc101/Andrey_Dyukmedzhiev/10points.gif

EDIT 2: The procedure is for ANY number of points, but the amount of calculations increases considerably and even for the points in Your example I didn't do them by hand. Let's take first 4 of them for convenience: (0,2), (2,4), (5,6), (5,10) - we should check first whether the required point isn't one of them /this is namely the case here - it is (2,4)!/. Take the 3 vectors, connecting (2,4) with the others:
V1(-2, -2), length(V1) = √((-2)² + (-2)²) = √8 ≈ 2.83
V2(3, 2), length(V2) = √(3² + 2²) = √13 ≈ 3.6,
V3(3, 6), length(V3) = √(3² + 6²) = √45 ≈ 6.7, so the unit vectors will be:
U1(-0.7, -0.7)
U2(0.83, 0.56)
U3(0.45, 0.9) and their sum
U1+U2+U3(0.58, 0.76) will have length 0.58² + 0.76² < 1, the latter means /condition (2)/ that (2,4) is the optimal point.

If the check shows that no point from the given set satisfies condition (2) /this is the case with the all 10 original points, the check is too lengthy!/, then we should solve the system of 2 equations in condition (1) for both coordinates x, y of the optimal point. I did just that and obtained the result in EDIT part above.

Follow the link to my other answer and read it carefully, I'm sure You'll get it in principle. The necessary calculations are another thing.