CS 506 Homework 2. Due by in class thursday Feb 20. Accepted without penalty until NOON Friday, Feb 21.

Unless otherwise stated, you may assume that objects are in general position. For example, you may assume that no two points have the same x-coordinate, no three points are collinear, no four points are cocircular. Also, unless otherwise stated, you may assume that any geometric primitive involving a constant number of objects each of constant complexity can be computed in O(1) time. Unless otherwise stated, you may use any method that you recall from class as a subroutine. More credit for clear answers that solve part of a question than for obscure confusing answers.

1. (5 points total) In a fully triangulated planar subdivision, every edge (for instance e) connects two corners of a quadrilateral. [Expected answer length: 1/2 page, with a small picture]
   1. (2 points) Given a pointer to an edge e in the DCEL structure, explain how to list all 4 edges of the quadrilateral enclosing edge e. e.next, e.prev, e.twin.next, e.twin.prev
      e.next, e.next.next, e.twin.next, e.twin.next.next
   2. (3 points) An edge flip is an operation that switches the diagonal of a quadrilateral. Give the updates to the DCEL structure for an edge flip. You only need to worry about creating correct ``next'' pointers for each edge of the quadrilateral and the new, flipped edge (f and f.twin).

   let the flipped diagonal be f.
   
   define e1 = e.next
   define e2 = e.next.next
   define e3 = e.twin.next
   define e4 = e.twin.next.next
   
   f.next = e4        e4.prev = f;
   e4.next = e1       e1.prev = e4
   e1.next = f        f.prev  = e1
   f.twin.next = e2   e2.prev = f.twin
   e2.next = e3       e3.prev = e2
   e3.next = f.twin   f.twin.prev = e3
   
   
   
   5 points You are given a pair of vertical lines x0 and
   x1, which define a vertical strip in the plane. You are also
   given a set L of n nonvertical lines, ei: y = ai x - bi. Present
   an O(n log n) time algorithm that counts the number of intersections
   of the lines of L within this strip. (Thus, the output consists of a
   single number.) You may make whatever general position assumptions are
   convenient.  [NOTE: this is not segment intersections, these are
   infinite lines, every line intersects every other line --- but you
   have to count how many of those intersections occur in the vertical
   strip.  Expected answer length may vary between 1/3-1 page.  small picture.]
   
   
   calculate the intersection of each input line with the first and
   second vertical line.  Sort each line by its intersection point (say,
   from bottom to top).  Let fi be the position of line i in
   the sorted list, so if line i has the LOWEST intersection with the
   first vertical line, then fi = 1.  Let gi be the
   position of line i in the sorted list of intersections with the second
   vertical line.  The sum, for all lines i, of absolute
   value(fi - gi) = 2 times the total number of
   intersections.  Why?  consider one line.  If it is 3rd from the bottom
   as it crosses the left vertical line, and 6th from the bottom as it
   crosses the right vertical line, then it must have crossed at least
   three lines.  
   
   ok... so this solution is mostly right.  until you actually try an
   example.  Try it, really, right now.  with three lines.  it doesn't
   work.  (if it did, try a different three lines).  So what is really
   going on?  
   
   think of the lines in order from bottom to top along the left vertical
   line.  (label these lines 1,2,3,4,5,...n) as i slide this vertical
   line slowly to the right, the order of these lines starts to change.
   That is, if the first intersection is between the very bottom-most
   lines, then this order becomes 2,1,3,4,5,...
   
   every intersection is a change in this order.  The total number of
   order changes is the number of intersection.  So how can we count the
   number of order changes?
   
   Naive algorithm: (bubble sort).
   for i = 1:n-1
    for j = 1:n-1
     for k = 1:n-1
      if list(k)>list(k+1) 
        swap(list(k),list(k+1))
        increment swap_counter
      end
     end
    end
   end
   
   output("The total number of lines is: ", swap_counter)
   
   It turns out that there is an O(n log n) algorithm for this, instead
   of the O(n^3) bubble sort algorithm.  How does this algorithm work?
   
   Algorithm Inversion Counter(L)    
   Input: Given a permutation of the numbers from 1..n.
   Output: L, sorted, and the number of swaps that would have been
             necessary to sort L
   CopOut: Assume n is a power of 2.
   
   if |L| = 1
     return L and 0  (one element list is already sorted with no swaps)
   else
     L1,count1 = InversionCounter( first half of L)     (recurse 1)
     L2,count2 = InversionCounter( second half of L)    (recurse 2)
     count = 0
     while |L2| > 0
       if first(L2) < first(L1)
         count = count + |L1|                % how many swaps would it
                                             % take to move this element
   					  % past all the elements in L1 into the
   					  % first spot...
         pop(L2)
       else
         pop(L1)  
     end
   
     return (sorted merged lists L1,L2), count+count1+count2
   end
   
   
   
   (6 points total) We often assume that our input is given in
   general position.  In this problem you are going to create an algorithm
   to check for this.  You are given n points, p1, p2, ... pn:
   (2 points) Give an O(n3) algorithm that determines if
   there are any 3 points that are collinear. [Expected answer length,
     about 5 lines, two of which start with ``for ? = 1 to n'']
   (4 points) Give an O( n2 log n) algorithm that determines
   if there are any 3 points that are collinear. [Expected answer length
   about 2/3 page, includes the word ``dual'', and explains WHY your
   algorithm does what it does.]