Member Avatar for 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.

  • 4 Contributors
  • 6 Replies
  • 152 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by siddhant3s
Member Avatar for Salem

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

So which bit is confusing you?

Member Avatar for still_learning

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

Member Avatar for 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.

commented: Yes indeed, start with paper and think! +32
Member Avatar for 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. :)

Member Avatar for 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.

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.