Simple Time Complexity Question

[still_learning]

I am working on solving several problems and this is one that I came across which I am not sure how to solve. If someone could help me here that would be great. Here is the problem, thanks much in advance:

Your boss comes up with the following idea: Move the store closer to the customers’ locations to improve sales. He suggests to analyze the current customer address data to select a location from m potential sites such that it has the most customers within a radius of R miles from the store. Let us assume that both the customer location data and the potential sites are in the form of (x,y) co-ordinates. Let us say there are n customer households. Write the algorithm and find out the time complexity for the algorithm (in terms of n and m). Note that given two locations (x1, y1) and (x2, y2), distance between them can be calculated by the following formula: √ (x2 - x1)2 + (y2 - y1)2.

[Salem]

> Write the algorithm and find out the time complexity for the algorithm

So which bit is confusing you?

[still_learning]

The algorithm is confusing me for starters. I don't know where to begin really.

[vmanes]

Imagine you have it all drawn out on paper - the locations of customers and the potential store sites. How would you solve it manually? Approach it from a strictly procedural method - don't assume anything that you as a human might see from the particular data set. Rather, how would you tell someone else how to find the best location.

[siddhant3s]

Start with two coordinates. It is trivial that the position of the store in this case would be the mid point of the line joining the two coordinate.
Now start with three coordinates. The most suitable location in this case would be a point from which, all the three points are equidistant. Mathematics tell me that such a point will exist.(There is a name given to the point which equidistant from the three vertices of a triangle. Find out what it is called.)

After you have cracked it for three points, think more about how will you find the solution for four or more points.

I remember, a similar problem was asked to me in some programming competition. :)

[vmanes]

siddhant3s - you misread the problem. It's not about finding the equidistant point - it's about finding which (store) point from some set has the largest number of clients within a given radius.

[siddhant3s]

>you misread the problem
Yes you are right. Well, here is what I 'thought' the problem was( I don't know if it is relevant here, but I don't feel like leaving the solution posed above orphan )
"Given the location of N customers , find out the location of the store such that all the customers are at a minimum distance R. Minimize R"

Now coming to the problem itself(I reread it). I have not put forward enough time to solve the problem,but the most obvious solution that comes into my mind is of complexity n times m.
I think it could be improved. Will think over it. Anyone with better algorithm? Don't post the algorithm, just its complexity.