Mazdak Farrokhzad edited proof b.tex  about 10 years ago

Commit id: a341607c43891fed36bbbf9d77d033de71d87596

deletions | additions      

       

\subsection{b)}  Consider running  the proof for task a), above algorithm,  butnow  with $I_1$ as the first interval ending after $R$ chosen to be  an arbitrary starting point $P$. If $start(I_1) \geq P$, the case is equivalent with  above, and it is possible to find the optimal solution. If $start(I_1) < P$, it  is possible that there exists ray,  instead of  one or more intervals $I_n$ such that  $start(I_1) \mod{2\pi} \leq end(I_n) < P$. If which does not intersect any of  the intervals. The  algorithm adds will  then select  the interval $I_1$, which is the interval which ends first after $R$. A  ray $R_n$ $R_1$  withan  angle in the $end(I_1)$ will be chosen to intersect $I_1$. Since  $angle(R) \leq end(I_1) = angle(R_1)$, and $I_1$ is chosen such that for any all intervals  $I_k, end(I_k) \geq angle(R) \implies end(I_k) >= end(I_1)$, any  interval $[start(I_1), end(I_n)]$, it intersected by $R$  is possible also intersected by $R_1$.  Now, consider removing all intervals intersected by $R_1$. This means  thatthe ray  $R_1$added at  $end(I_1)$  will not be needed, needed any more,  and could possibly can  be removed. The rest Since any interval intersected by $R$ is  also intersected by $R_1$, and all intervals intersected by $R_1$ have been removed,  $R$ no longer intersects any interval. Thus, by removing the first ray and the  intervals which it intersects, the problem is converted to the special case which  we proved that our algorithm can find the optimal solution for earlier.  Since the algorithm ignores any interval which has already been intersected by an  earlier ray, the step  of choosing  the rays  will always be needed, since first ray is equivalent to  removing any the  intervals intersected by it. Thus, the remaining part  of them the problem will be solved  with a solution which  would cause at least one circle have been optimal if the intervals intersected by the  first ray were  not present.  Since the smaller problem is a subset of the larger problem, and any interval  intersected by a ray in the optimal solution to the smaller problem still needs  to be intersected any more. This means that by a ray in  the result might have larger problem, it is impossible to solve the  larger problem with fewer rays than the smaller problem. Since our algorithm uses  only  one more ray to solve the larger problem, it is impossible for a solution  which uses more  than optimal, but not more. one ray less than our solution to exist, since such a  solution would have fewer rays than needed to solve the smaller problem, which  is a contradiction.