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:

Abstract pseudocode

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

More detailed version

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