deletions | additions
diff --git a/proof-a.tex b/proof-a.tex
index a6e3427..d4da0af 100644
--- a/proof-a.tex
+++ b/proof-a.tex
...
Assume that we have added the intervals to a priority queue as described above. The
properties of the queue will ensure that we will get the intervals ordered by ending
angle, i.e.
I_1 $I_1$ will have an ending angle smaller than or equal to
I_2 $I_2$ etc.
Consider retrieving the first interval
I_1 $I_1$ from the queue. This interval has the
property that for all intervals
I_n in $I_n \in Q, end(I_1) <=
end(I_n). end(I_n)$. For a solution to be
valid, it must contain a ray
R_1, $R_1$, such that
start(I_1) $start(I_1) >= angle(R_1) >=
end(I_1); end(I_1)$;
otherwise, the circle corresponding to
I_1 $I_1$ would not be intersected by any ray.
Since any interval
I_k in Q $I_k \in Q$ where
start(I_k) $start(I_k) <=
end(I_1) end(I_1)$ also has the property that
end(I_k) $end(I_k) >=
end(I_1), end(I_1)$, all these intervals can be intersected by a ray with angle
end(I_1). $end(I_1)$. No ray with an angle in
I_1 $I_1$ can intersect more intervals than the ray at
end(I_1). $end(I_1)$. If it could, this would mean that there was an interval ending before
end(I_1), $end(I_1)$, but since we chose
I_1 $I_1$ to be the interval ending first, this is a
contradiction. This means that our first ray
R_1, $R_1$, will intersect at least as many
circles as any ray intersecting
I_1 $I_1$ in an optimal solution.
For the remaining intervals in
Q, $Q$, any interval intersected by an earlier ray will be
ignored. Since
R_1 $R_1$ was added at the end of
I_1, $I_1$, and all intervals intersected by
R_1 $R_1$
are ignored, this means that the first interval that is not ignored,
I_2, $I_2$, will not
intersect
I_1. $I_1$. This in turn means that since
end(I_1) $end(I_1) <
start(I_2), start(I_2)$, it is impossible
to find a ray
R $R$ such that
start(I_2) $start(I_2) <= angle(R) <=
end(I_1), end(I_1)$, and thus, a separate
ray,
R_2 $R_2$ is required in order to intersect
I_2. $I_2$.
Since
I_2 $I_2$ was chosen such that all intervals
I_k $I_k$ where
end(I_k) $end(I_k) <
end(I_2) end(I_2)$ will
already have been intersected by
R_1, $R_$1, we are back in a case equivalent to that of
I_1, $I_1$, but with fewer elements in
Q. $Q$. This means that the ray
R_2 $R_2$ at
end(I_2) $end(I_2)$ will
also intersect as many intervals not already intersected by
R_1 $R_1$ as a ray within
I_2 $I_2$
can. Since all solutions need to have at least one ray within
I_1, $I_1$, and one ray
within
I_2, R_1 $I_2, R_1$ and
R_2 $R_2$ will intersect at least as many circles as any rays through
I_1 $I_1$ and
I_2 $I_2$ in an optimal solution will do.
This argument can be repeated for
I_3, $I_3, I_4, ...
I_n, I_n$, until no more intervals remain
in the queue. Since for each step,
I_m $I_m$ will not intersect
I_{m-1}, I_m $I_{m-1}$, $I_m$ is chosen
such that all intervals
I_k $I_k$ where
end(I_k) $end(I_k) <
end(I_m) end(I_m)$ are intersected by one or
more of the rays
R_1, $R_1, R_2, ...,
R_{m-1}, R_{m-1}$, there must exist a ray
R_m $R_m$ such that
start(I_m) $start(I_m) <= R_m <=
end(R_m), end(R_m)$, and this ray is chosen so that any interval
I_l $I_l$
where
end(I_{m-1}) $end(I_{m-1}) < start(I_l) <= end(I_m) <=
end(I_l) end(I_l)$ is intersected by it, this
means that our algorithm will use no more rays than required to intersect all
circles in the interval
[start(I_1), end(I_m). $[start(I_1), end(I_m)$. Therefore, our solution will
always be optimal.
