All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

I discussed the meaning of plane scanning for #4 with Jeff Green.

  1. There is an algorithm for finding the convex hull that takes O(hn) time where h is the number of points on the hull. Show that there can be Ω(n) points on the convex hull, making the worst case Ω(n2).

    Every point on the convex hull achieved through either a Graham Scan or Gift Wrapping will consist of line segments whose endpoints are elements of the set of points to be contained by the hull. The maximum number of points in the hull therefore is n.

    The convex hull is a convex polygon. A set of points that defines a convex polygon will therefore be the same as a convex hull for those points. (Since there's only a single convex polygon for a set of points that polygon has to be the same as the hull.)

    A simple method for arranging a set of points into a convex polygon is to arrange them on a circle some distance from a center point not an element of the set. The line segments of the polygon are then found by sequentially joining the points in the order they appear while traveling around the circle.

    This works because all the points are a fixed distance from the center point. All line segments start and end the same distance from the center of the polygon. A concavity for such a polygon would rely on a point being closer to the center than the ones to either side and this isn't possible.

    This arrangements therefore makes a convex polygon from n points which would make the convex hull require n points and the execution time of Gift Wrapping will be O(n2).

  2. Since the bounds O(hn) and O(n log n) are incomparable, a good approach is to run the two algorithms in "pseudo-parallel." In a pseudo-parallel algorithm, two algorithms are run simultaneously, alternating a step of one algorithm with a step of the other, until one algorithm terminates. If the worst case running time of algorithm A is Θ(fA(n)) and the worst case running time of algorithm B is Θ(fB(n)), show that the worst case running time of running A and B in pseudo-parallel is O(min(fA(n), fB(n)).

    This really depends on the definition of the term, "step." A step could be considered in terms of a time slice for a multiprocess operating system. Each algorithm is allowed access to the hardware and conducts a fixed number of operations. In this situation if all programs are given equal priority and equal time slices the length of time to execute any two algorithms simultaneously will simply be double the time for executing a single one (neglecting process switching overhead).

    Programming wise this method of pseudo-parallelism would correspond to two separate processes running on an operating system on a single processor with a single core. Another model is a multi-threaded program. This model allows for a different concept of "step" because each algorithm can signal when a "step" has completed through use of a mutex. This model makes more sense for the purpose of this question because it makes it possible for the programs to run simultaneously in something other than a constant times the original running time.

    The two algorithms in question are:

    • Gift Wrapping:
      1. Step 1: Find the anchor point with minimum y.
      2. Steps 2 to hn + 1: Finding pi such that all points are to the right of the line between pi - 1 and pi. This takes O(n) time.
    • Graham Scan:
      1. Step 1: Find the anchor point with minimum y.
      2. Steps 2 to n + 1: Add a point to the heap sorted by angle relative to anchor point. This takes O(log n) time.
      3. Step n + 2: Build convex hull. This takes O(n) time.

    Each of these steps takes roughly equivalent time. If h < log n then gift wrapping will terminate while the Graham Scan is still building its heap. After the heap is done, Graham Scan will build the hull in the time it takes Gift Wrapping to find a single point.

  3. Design two algorithms, A and B, with worst case running times Θ(fA(n)) and Θ(fB(n)) respectively such that the worst case running time of these two algorithms in parallel is not Ω(min(fA(n), fB(n)).

    For time slicing this is not possible. The running time of one process cannot slow others beyond the time and resources allotted by the operating system. (Resource hungry processes at times will slow a system and other processes, but this is a controllable result of resource allocation by the operating system.)

    When the program defines the steps however, all that is required is improper definition of a step. Say for instance in the previous example that instead of adding the points to the heap for Graham Scan one at a time that they were all added in one step. That step would then take O(n log n) time and the pseudo-parallel algorithm would take O(n log n) regardless of whether h is less than log n or not.

  4. Show that you can determine whether there are intersections among a set of n line segments in O(n log n) time, even if the lines are not simply horizontal and vertical. (Hint: Plane sweep still works.)

    The basic idea of plane sweep is the points are placed in a queue based on the leftmost point (minimum point). A second queue is made with the order of the rightmost points that correspond to the sorted left point. One at a time the element with the minimum x is processed from each of those queues. Generating these queues will take O(n log n) for the sorting. Processing these elements corresponds conceptually to a line passing from left to right and processing the start and end of lines as they are reached.

    Some computation is done as a line is started or ended. At any given time there is a set of lines that the scanline intersects. These are easily managed by adding them to the queue when the start point is processed and removing them when the endpoint is removed. Any intersection between two lines will have to occur while those lines are a part of the set of active lines.

    Using this fact, a line can be tested for intersections with the set of active lines when it enters the set. Doing this alone would generate O(n2) potential comparisons. To limit this growth requires limiting the number of comparisons. This can be done by considering that if a line segment will have an intersection, it will have to include the lines either directly above or below. Finding these lines can be found in O(log n) time by keeping the lines ordered by the x-coordinate in a tree.

    This tree will need to reordered at three times. When a line is added, when a line ends, or when an intersection is passed since that necessarily represents a change in which line is above the other. The order of those two lines may simply be flipped in constant time.