Finding minimum number of rays to intersect all arcs

Question

There is a question in Elements of Programming Interviews that I have tried to solve but was unsuccessful. Assume we are given an array of intervals of the form (d1, d2) where d1 and d2 are values in degrees representing the start and end angles of an arc, where 0 degrees is the y-axis. These intervals can overlap, and you can have an interval like (350, 10). What is the minimum number of rays you can shoot to intersect all the intervals? A ray can be represented as an angle in degrees from the y-axis.

I've tried sorting by endpoints and seeing if each endpoint intersects wit hthe next interval, but I couldn't figure out how to deal with the overlapping intervals such as (340, 350), (350, 20).

Answer 1

1. create table tab of all used angles (interval edges)

   should contain only distinct angles

2. set all arcs as unused

3. find angle from tab which intersects most unused arc's

4. add it as ray

5. exclude this angle from tab

6. set all intersected rays as used

7. loop #2 until no unused arc or angle is left

This will significantly decrease the number of rays but will not ensure optimal solution !!! For really optimal solution you would need to use genere & test approach instead. Here some C++ code for this:

#include <math.h>
struct _arc
    {
    int d0,d1;  // [deg] CW arc angular interval
    int flag;   // temp
    };
const int N=8;  // number of arcs
_arc arc[N];    // arcs table
int ray[N+N],rays=0;    // rays table and number of rays
//---------------------------------------------------------------------------
void generate()
    {
    int i;
    _arc *a;
    for (a=arc,i=0;i<N;i++,a++)
        {
        a->d0=Random(361);
        a->d1=Random(361);
        a->flag=0;
        }
    }
//---------------------------------------------------------------------------
void solve()
    {
    int i,j,k,e,d0,d1,d,n0,n1;
    _arc *a;
    int tab[N+N],n;
    rays=0;
    // clear flag and make a asc sorted list of angles
    for (i=0;i<N+N;i++) tab[i]=0;
    for (a=arc,i=0,n=0;i<N;i++,a++)
        {
        a->flag=0;
        // insert d0
        for (d=a->d0,j=0;j<n;j++)
            {
            if (tab[j]==d) { j=-1; break; }
            if (tab[j]> d) { for (k=n;k>j;k--) tab[k]=tab[k-1]; tab[j]=d; n++; j=-1; break; }
            } if (j>=0) { tab[n]=d; n++; }
        // insert d1
        for (d=a->d0,j=0;j<n;j++)
            {
            if (tab[j]==d) { j=-1; break; }
            if (tab[j]> d) { for (k=n;k>j;k--) tab[k]=tab[k-1]; tab[j]=d; n++; j=-1; break; }
            } if (j>=0) { tab[n]=d; n++; }
        }
    // find ray with max number of overlaps
    for (e=1;e;)    // loop while not all arcs done
        {
        e=0;
        for (n1=0,k=-1,j=0;j<n;j++)
            {
            // count intersections into d0
            d=tab[j]; n0=0; if (d<0) continue;
            for (a=arc,i=0;i<N;i++,a++)
             if (a->flag==0) // skip already done arcs
                {
                d0=a->d0;
                d1=a->d1;
                if (d0>d1) { if ((d>=d0)||(d<=d1)) n0++; }
                else       { if ((d>=d0)&&(d<=d1)) n0++; }
                }
            // remember max k-index, d1-intersections
            if (n1<n0) { k=j; n1=n0; }
            }

        if (!n1) break; // stop if no angle left (error)
        // add ray
        ray[rays]=tab[k]; rays++;
        // exclude arcs
        d=tab[k];
        for (a=arc,i=0;i<N;i++,a++)
         if (a->flag==0) // skip already done arcs
            {
            e=1;
            d0=a->d0;
            d1=a->d1;
            if (d0>d1) { if ((d>=d0)||(d<=d1)) a->flag=1; }
            else       { if ((d>=d0)&&(d<=d1)) a->flag=1; }
            }
        }

    // debug: set flag=1 for ray intersected arces (for visual check)
    for (a=arc,i=0;i<N;i++,a++)
     for (a->flag=0,j=0;j<rays;j++)
        {
        d =ray[j];
        d0=a->d0;
        d1=a->d1;
        if (d0>d1) { if ((d>=d0)||(d<=d1)) a->flag=1; }
        else       { if ((d>=d0)&&(d<=d1)) a->flag=1; }
        }
    }

And overview:

As you can see it cast the rays through edge points if you need different rays you need to tweak this a bit (like use mid angle of the common overlap that would lead to more rays of coarse). The code is far from optimized I coded it just for fun right now ...

To improve this you can sort the lists and use ranged searches instead (similar to merging sorted lists) In current state of code there is no advantage taken from the sorting ...

Answer 2

to optimize the number of arcs, you CAN'T throw a ray from A to B and another ray from C to D if A and C intersect, for example.

the keypoint is to find all the intersection points between arcs (and sort them by the points that belong to more arcs).

After you sort them, get the angle that belong to more arcs and set a ray from it to another point that belong to some other set of arcs different from the first. The most different, the better. You can just travel the angles and check for the one that fits the best.

Answer 3

Assuming the degrees are Integers:

1. loop through to find all degrees which are -1 starting angle and +1 ending angle
2. Treat arcs as intervals, search to see if there is a point from 1. which is uncovered
3. If yes we'll use that point to start the greedy strategy of take the best shot
4. If no - than return the least set of intervals which cover all the points from 1. remove these intervals from consideration and try to find a starting point without these intervals, start there and use the same greedy strategy in 3, merging results back with the best results for the removed intervals.

For example

def algo:
  results = [] # will be an array of angles that represent the best shots
  I = [(start,end)] #array of starting and ending degrees
  P = getAnglesOutOfRange() # where this func just returns an array of points
                            # which are not covered by the starting and ending
                            # angles in I (+1 starting, -1 ending) mod 360
  
  obj = intervalPointCoverForArcs(P,I) 

  # if obj is a point than we have the starting point to start shooting.
  # Sort intervals by ascending starting angle, then iterate over queue
  # performing greedy strategy of shooting just inside the least ending angle
  # of overlapping intervals. 

  # if obj is a set of intervals than remove those intervals from I and recursively
  # call this function - the recursive call will return a list of
  # angles which will make up the best shots for the subset of intervals.
  # Perform a merge operation to determine which intervals still need to be covered 
  # by a point and remove those intervals with the same greedy strategy. 

return results

def intervalPointCoverForArcs(P,I):
  # Were P is a set of points and I is a set of intervals
  results = []; Last = -inf; end_init = -inf;
  I_max = SelectMax(I)  # Function that grabs the interval with the latest starting
                        # angle.
                        # We choose starting angle because we want to see if the ending
                        # angle crosses the 0 axis.
  if I_max.end > 360: 
    end_init = I_max.end # Tracking that this interval overlaps the 0 axis
                         # So any points less than this amount will be covered
    
    I_max.end = I_max.end + 360 # increasing the initial intervals' ending value 
                                # to go past 0 axis
  
  I_init = (-inf,end_init) # this will be the first item deleted from the items
                           # PriorityQueue below since it's starting angle is initialized
                           # to -inf
  I.append(I_init)
  activated_intervals = PriorityQueue() # Empty queue to start - queue will be sorted by
                                       # descending ending angles
  items = PriorityQueue(I,P) # Function which combines the Intervals and Points returning
                             # an ascending sorted order of points and 
                             # interval starting angle
  while not items.isEmpty():
    i = items.delete()
    
    if isinstance(i, set): 
      activated_intervals.insert(i)
    elif i > Last: 
      k = activated_intervals.delete()
      
      if k.end < i: 
        return i # this is our starting point as no interval covers it
      else:
        Last = k.end
        result.append(k)  # Track this interval as it's covering the most points and
                          # we may want to remove later in case all the points are covered
  return results