7
$\begingroup$

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)

9balloons-4rays

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.

$\endgroup$
  • $\begingroup$ 'our greedy algorithm says that this ray will intersect the most objects' I don't see how this statement is justified. The most objects of what set of possible directions? $\endgroup$ – jwg Sep 6 '17 at 7:50
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer! It's starting to get clearer for me now. However now I need to figure out a basic idea of how to make this algorithm O(n log n). Would you happen to have any beginning thoughts? thanks again! $\endgroup$ – pinoyboy Jan 26 '16 at 5:29
  • $\begingroup$ @pinoyboy $n \log n$? Well, it often means that you can first sort some things. Maybe sort all the balloons by the angles of their right (clockwise again) tangle lines. Then it is easy to apply the greedy strategy. $\endgroup$ – hengxin Jan 26 '16 at 5:44
  • $\begingroup$ Ahhh, that makes sense! I'm so sorry for asking so many questions. But it's making a lot of sense to me now! $\endgroup$ – pinoyboy Jan 26 '16 at 5:47
  • $\begingroup$ @pinoyboy Glad to help. Note that I did not prove it formally. You should try it. Trying to prove a greedy strategy is a good chance to learn. $\endgroup$ – hengxin Jan 26 '16 at 5:52
  • 1
    $\begingroup$ How would you handle the case where there is no direction initially along which a ray will not intersect any balloon? Starting an algorithm from an arbitrary angle in this case doesn't seem to lead to an optimal solution... $\endgroup$ – Max Lawnboy Nov 9 '18 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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