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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.