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.

Answered by Salem 5,138 in a post from

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

So which bit is confusing you?

Answered by vmanes 1,165 in a post from

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 …

## All 6 Replies

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

So which bit is confusing you?

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

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.

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. :)

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.