Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Suppose I have a set of points on a plane and I want cover them in or on a circle of radius r. I want to minimize the number of circles I use. What would be an appropriate greedy approach to this problem? Personally, I would sort the points by x axis, and starting from the first point, place the centre of my circle as far as possible (distance r) from the point, then repeat for other points; if the next point is on the circle ignore this point, else repeat what I just did. Is my approach greedy?

share|improve this question
What are the restrictions that make you use more than one circle? – Raphael Jan 18 '12 at 12:53
1  
@Raphael: I suppose that radius r is given as part of input. – Tsuyoshi Ito Jan 19 '12 at 2:36

1 Answer

up vote 1 down vote accepted

A greedy approach is just an approach that, at each step, does what's optimal at that step, without looking to see what might be the consequences for the situation some number of steps ahead. So your approach is certainly a greedy approach. A more interesting question, I think, and one which I cannot answer, is whether your approach is optimal, or even whether it is optimal among all greedy approaches.

share|improve this answer
What exactly make a greedy algorithm? How do I tell when I am using a greedy algorithm? – Mark Jan 18 '12 at 0:02
In your example, each time you choose a circle, you choose it to cover as many points as possible (in addition to the leftmost not-yet-covered point); that makes it a greedy algorithm. It solves as much of the problem as it can at each step. If that doesn't help. you may find the discussion at en.wikipedia.org/wiki/Greedy_algorithm useful, if you get there before the 24-hour blackout. – Gerry Myerson Jan 18 '12 at 0:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.