Greedy strategy for computing the minimum number of rays that hit all balloons

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 t

Principle: You need to shoot the rays in some order and choose carefully the proper direction/angle for the first ray.


$Q_1:$ 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?

See the figure in the problem. Suppose there are only 4 balloons: the two green ones and the two blue ones. If you shoot your first ray along the x-axis (this is allowed by your greedy strategy. note that I suppose that the three bigger balloons cannot be hit by a single ray; otherwise, move them around slightly), you will leave the two other balloons far apart. As a result, it costs you 3 rays, but the optimal is 2.


$Q_2:$ What is the point of the fact that there is a ray that does not intersect any balloons?

So the key point is to shoot the first ray along the right direction. Here comes the fact that "there is a ray that does not intersect any balloons".

The basic idea is as follows:

• first find the direction/angle $\alpha$ along which a ray does not intersect any balloons;

• then identify the first balloon (say, clockwise) $b$ with respect to this direction/angle $\alpha$; Here $b$ is defined to be the first balloon you leave when you sweep a line starting from the direction/angle $\alpha$ clockwise.

• shoot a ray which is $b$'s rightmost (clockwise) tangent line $l$， remote all balloons hit by $l$,

• and then recurse.

$Q_3:$ Am I supposed to prove that some optimal solution uses this fact?

It is not easy to prove a greedy strategy is correct. You can try to prove the idea above by applying mathematical induction and exchange argument (or maybe show it is wrong!). A hint is to consider the set of rays shot by an arbitrary algorithm, sort them by angles with respect to $\alpha$ (clockwise), then compare it to the optimal solution one by one.

Implementation: In the comments, OP asks for an $n \log n$ algorithm. Well, $n \lg n$ often means that you can sort some things first. Maybe sort all the balloons by the angles of their right (clockwise again) tangle lines. Then it is easy to apply the greedy strategy above.
This is a rough idea. How to implement it efficiently by choosing/designing good data structures is left as an exercise.

StackExchange Computer Science Q#52291, answer score: 2