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.
   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).

2. 5 points You are given a pair of vertical lines x₀ and x₁, which define a vertical strip in the plane. You are also given a set L of n nonvertical lines, e_i: y = a_i x - b_i. 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.]

3. (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, p₁, p₂, ... p_n:
   1. (2 points) Give an O(n³) 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'']
   2. (4 points) Give an O( n² 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.]