0
$\begingroup$

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?

  • 1
    @Raphael: I suppose that radius r is given as part of input.2012-01-19

1 Answers 1

1

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.

  • 0
    In your ex$a$mple, each time you choose a circle, you choose it to cover as many points as possi$b$le (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 http://en.wikipedia.org/wiki/Greedy_algorithm useful, if you get there before the 24-hour blackout.2012-01-18