ROUGH DRAFT authorea.com/5957
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Algorithms - Lab 2, Problem 2

    Introduction

    This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.

    Group 7 consists of:

    • Mazdak Farrokhzad

      • 901011-0279

      • twingoow@gmail.com

      • Program: IT

    • Niclas Alexandersson

      • 920203-0111

      • nicale@student.chalmers.se

      • Program: IT

    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.

    Pseudocode

    We’ll first assume that we have access to the following constant time subroutines:

    [H]

    [1] …

    [H]

    [1] …

    Abstract pseudocode

    [H]

    [1] convert add ray at end of \(I\) number of rays

    More detailed version

    [H]

    [1] add \([A_{min}, A_{max}]\) to \(Q\) \(N_R\)

    Proof

    a)

    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\) will have an ending angle smaller than or equal to \(I_2\) etc.

    Consider retrieving the first interval \(I_1\) from the queue. This interval has the property that \(\forall I_n \in Q : \left[end(I_1) \leq end(I_n)\right]\). For a solution to be valid, it must contain a ray \(R_1\), such that \(start(I_1) \geq angle(R_1) \geq end(I_1)\); otherwise, the circle corresponding to \(I_1\) would not be intersected by any ray.

    Since any interval \(I_k \in Q\) where \(start(I_k) \leq end(I_1)\) also has the property that \(end(I_k) \geq end(I_1)\), all these intervals can be intersected by a ray with angle \(end(I_1)\). No ray with an angle in \(I_1\) can intersect more intervals than the ray at \(end(I_1)\). If it could, this would mean that there was an interval ending before \(end(I_1)\), but since we chose \(I_1\) to be the interval ending first, this is a contradiction. This means that our first ray \(R_1\), will intersect at least as many circles as any ray intersecting \(I_1\) in an optimal solution.

    For the remaining intervals in \(Q\), any interval intersected by an earlier ray will be ignored. Since \(R_1\) was added at the end of \(I_1\), and all intervals intersected by \(R_1\) are ignored, this means that the first interval that is not ignored, \(I_2\), will not intersect \(I_1\). This in turn means that since \(end(I_1) < start(I_2)\), it is impossible to find a ray \(R\) such that \(start(I_2) \leq angle(R) \leq end(I_1)\), and thus, a separate ray, \(R_2\) is required in order to intersect \(I_2\).

    Since \(I_2\) was chosen such that all intervals \(I_k\) where \(end(I_k) < end(I_2)\) will already have been intersected by \(R_1\), we are back in a case equivalent to that of \(I_1\), but with fewer elements in \(Q\). This means that the ray \(R_2\) at \(end(I_2)\) will also intersect as many intervals not already intersected by \(R_1\) as a ray within \(I_2\) can. Since all solutions need to have at least one ray within \(I_1\), and one ray within \(I_2, R_1\) and \(R_2\) will intersect at least as many circles as any rays through \(I_1\) and \(I_2\) in an optimal solution will do.

    This argument can be repeated for \(I_3, I_4, ... I_n\), until no more intervals remain in the queue. Since for each step, \(I_m\) will not intersect \(I_{m-1}\), \(I_m\) is chosen such that all intervals \(I_k\) where \(end(I_k) < end(I_m)\) are intersected by one or more of the rays \(R_1, R_2, ..., R_{m-1}\), there must exist a ray \(R_m\) such that \(start(I_m) \leq R_m \leq end(R_m)\), and this ray is chosen so that any interval \(I_l\) where \(end(I_{m-1}) < start(I_l) \leq end(I_m) \leq 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)]\). Therefore, our solution will always be optimal.