this is for holding javascript data
Mazdak Farrokhzad added description.tex
about 10 years ago
Commit id: 70ec0eaea13fc4a2d232332f8e8dfadf18e06572
deletions | additions
diff --git a/description.tex b/description.tex
new file mode 100644
index 0000000..04f2a5a
--- /dev/null
+++ b/description.tex
...
\section{Description}
The following algorithm finds the number of rays originating from a specific point needed to intersect a number of circles in a plane.
The objective is to find the smallest number of rays needed to intersect all of the circles. Since the nature of this problem is not
one of geometry, and we know the position and radii of the circles, we'll assume that we can make any mathematical calculation involving
a single circle in constant time.
Under the above assumption, finding the minimum and maximum angles at which a ray will intersect a specific circle can be done in
constant time. These two angles make up the endpoints of an interval of angles within which a ray originating from the starting point
will intersect the circle. This means that a circle can be seen as an interval of angles instead of as a position as a radius, and
that the set of circles can be seen as a set of intervals. This makes the problem very similar to the interval scheduling problem.
A problem with this, though, is that we don't have any clearly defined starting angle. It may well be that the angle 0 is contained
within one of the intervals. However, for task a), we are allowed to assume that it is possible to find an angle at which a ray
would not intersect any of the circles. If we find this angle, we can use that as our starting point.
The rest of the problem can be solved in the same manner as the interval scheduling problem, by sorting the intervals according to
which interval ends first, and then adding a ray at the end of each interval which is not already intersected by an earlier ray.
For task b), we simply pick an arbitrary starting angle instead. Why this works will be proven later.
