The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm".
The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the plane, each specified by its radius and the $(x, y)$ coordinates of its center, compute the minimum number of rays from the origin that intersect every circle in $C$. Your goal is to find an efficient algorithm for this problem. (See a "9-balloons-with-4-rays" example in the figure below)
Question: Suppose it is possible to shoot a ray that does not intersect any balloons. Describe and analyze a greedy algorithm that solves the minimum zap problem in this special case.
I'm having trouble approaching this problem. I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?
And what is the point of the fact that there is a ray that does not intersect any balloons? Am I supposed to prove that some optimal solution uses this fact?
Any help would be appreciated! I just recently started learning algorithms :)
Algorithm based off of hengxin's answer: https://cs.stackexchange.com/a/52293/42816
Proof by mathematical induction
Note: Did not use O( n log n) implementation
Now we will prove the correctness of this algorithm using mathematical induction. We will show that our greedy algorithm cannot do worse than the optimal solution.
Let $S'$ be the set of rays shot by our greedy algorithm. Let $S$ be the set of rays shot by another optimal solution.
Our base case is when $n = 1$. There is only one object to destroy, and our greedy algorithm uses 1 ray, which also happens to be optimal. So this checks out.
Now for our induction hypothesis, we will assume that our greedy algorithm is optimal for up to $n$ objects.
We now claim that the first ray from $\alpha$ of $S'$ cannot do worse than that of $S$.
Now let's consider an $n+1$ object situation. Then, we sort $S'$ and $S$ according to $\alpha$, clockwise. Now let's examine the first ray that occurs from $\alpha$ clockwise. In $S'$, this first ray, call it $R'$, cannot possibly do worse than that of $S$, call it $R$, because our greedy algorithm says that this ray will intersect the most objects, including the first one from $\alpha$. Therefore, $R$ either intersects just as much or fewer objects than $R'$. Thus, we can replace $R$ with $R'$ in the optimal solution $S$.
Now, we have to figure out if the rest of $S'$ is optimal, cutting out $R'$, which we'll call $T'$. However, since there are now at most $n$ objects, our induction hypothesis says that our greedy algorithm finds an optimal solution to $T'$. As such, the $R' + T'$ problem has an optimal solution from our greedy algorithm. Q.E.D.