Problem:
Please find the problem here.
4 small ducks are in a large circular pond, and can each be at any point in the circle with equal chance. What is the probability that a diameter can be drawn so that all 4 ducks are in the same semicircle of the pond?
Solution:
Here is a partial solution to the problem - before we can compute the probability, we need to know a way (i.e. an algorithm) to determine whether or not the ducks are on the same semi-circle.
So this is a computational geometry problem, and we will use computational geometric techniques. Here we will use line sweep (angular sweep).
For simplicity, we simply design a coordinate system such that the pond is the unit circle.
Now, as a probe, let's check if all the ducks are in the upper semi-circle. If all the ducks have positive y coordinate, then we know they are all in the same semi circle, great.
Now, suppose we are not that lucky that some ducks actually have negative coordinate. We will move the diameter to fit them. Now here is the key intuition. Moving it just by a little bit is not going to work, one should move until we reach an 'event point'. If the diameter does not move pass a duck, nothing is going to change.
Therefore the algorithm is to sort the ducks in increasing phase (we model a duck by a complex number in the unit circle) and then we run the line sweep as mentioned above. For simplicity, we always use positive phase (i.e. $ [0, 2\pi) $)
Suppose the line is currently at the first duck with minimal phase $ p_1 $, if the last duck has phase $ p_1 + \pi > p_4 $, then we are good, they are all in the same semicircle.
Suppose that's not true, then we move our sweep line so that it is at the second duck. now we need to make sure the semi-circle contains the 1st duck. The mathematical condition for that to happen is $ p_2 + \pi > p_1 + 2\pi $.
Similarly, we get all these conditions.
$ p_1 + \pi > p_4 $
$ p_2 + \pi > p_1 + 2\pi $
$ p_3 + \pi > p_2 + 2\pi $
$ p_4 + \pi > p_3 + 2\pi $
We can now rearrange these equations into a more illuminating forms:
$ p_1 + 2\pi - p_4 > \pi $
$ p_2 - p_1 > \pi $
$ p_3 - p_2 > \pi $
$ p_4 - p_3 > \pi $
These equations can now be interpreted as the angles between the ducks, if any of these angle is larger than $ \pi $, then we know they fits in a semi-circle. Now can be easily programmed.
Please find the problem here.
4 small ducks are in a large circular pond, and can each be at any point in the circle with equal chance. What is the probability that a diameter can be drawn so that all 4 ducks are in the same semicircle of the pond?
Solution:
Here is a partial solution to the problem - before we can compute the probability, we need to know a way (i.e. an algorithm) to determine whether or not the ducks are on the same semi-circle.
So this is a computational geometry problem, and we will use computational geometric techniques. Here we will use line sweep (angular sweep).
For simplicity, we simply design a coordinate system such that the pond is the unit circle.
Now, as a probe, let's check if all the ducks are in the upper semi-circle. If all the ducks have positive y coordinate, then we know they are all in the same semi circle, great.
Now, suppose we are not that lucky that some ducks actually have negative coordinate. We will move the diameter to fit them. Now here is the key intuition. Moving it just by a little bit is not going to work, one should move until we reach an 'event point'. If the diameter does not move pass a duck, nothing is going to change.
Therefore the algorithm is to sort the ducks in increasing phase (we model a duck by a complex number in the unit circle) and then we run the line sweep as mentioned above. For simplicity, we always use positive phase (i.e. $ [0, 2\pi) $)
Suppose the line is currently at the first duck with minimal phase $ p_1 $, if the last duck has phase $ p_1 + \pi > p_4 $, then we are good, they are all in the same semicircle.
Suppose that's not true, then we move our sweep line so that it is at the second duck. now we need to make sure the semi-circle contains the 1st duck. The mathematical condition for that to happen is $ p_2 + \pi > p_1 + 2\pi $.
Similarly, we get all these conditions.
$ p_1 + \pi > p_4 $
$ p_2 + \pi > p_1 + 2\pi $
$ p_3 + \pi > p_2 + 2\pi $
$ p_4 + \pi > p_3 + 2\pi $
We can now rearrange these equations into a more illuminating forms:
$ p_1 + 2\pi - p_4 > \pi $
$ p_2 - p_1 > \pi $
$ p_3 - p_2 > \pi $
$ p_4 - p_3 > \pi $
These equations can now be interpreted as the angles between the ducks, if any of these angle is larger than $ \pi $, then we know they fits in a semi-circle. Now can be easily programmed.
No comments:
Post a Comment