Write an algorithm that takes two line segments as input

Question

1 Dimensions

1.1 Prove that a set of 3 points a, b, and c in the plane are collinear if and only if the vectors [^a₁], [^b₁], and [^c₁] are linearly dependent, i.e. one of these points can be written as a linear combination of the other two. Note, you should use the equation of the line through the points to define the linear dependence.

1.2 We say that affine dimension of a set of points is the dimension of the space of all affine combinations. A point is 0-dimensional. A line is 1-dimensional. A plane is 2-dimensional. This is a little different from the notion of dimension used for vector spaces. It is true that a 1-dimensional vector space is a line, but that means it can be represented as all linear combinations of a single vector. For a general line, we need at least two points. (This is the difference between vectors and points). Prove that the affine dimension of a set of points p1, ... ,pn ∈ R3 is one less than the dimension of the vector space spanned by [p11] , ... , [pn1].

1.3 Most of the time, question 1.2 means that the affine dimension of {p1, ... , p_n} is one less than the linear dimension of the same set of points when viewed as vectors. When is the affine dimension equal to the linear dimension?

2 Convexity

2.1 In class, we gave two different definitions of the convex closure of a set U ⊆ R^d:

1. CC(U) is the set of all convex combinations of the points of U.

2. CC(U) is the intersection of all convex sets containing U.

Prove these definitions are equivalent.

2.2 In class, we gave two different definitions to describe when a set U ⊆ R^d is convex:

1. U is convex iff U = CC(U).

2. U is convex iff for every pair of points a, b ∈ U, and all t ∈ [0, l] it is true that (1- t) a + tb ∈ U. Prove these definitions are equivalent.

3 Using Linear Predicates

3.1 Let ccw(a, b, c) be the counterclockwise test introduced in class. That is,

Use this predicate to write an algorithm that takes 4 points as input and decides whether or not they are in convex position (i.e. every point is on the convex hull). Do not assume general position. For this problem, we will say that the points are not in convex position if one of the points is on the line throughg two of the other points. Give some justification for why it is correct.

3.2 In class we saw how to check if two line segments intersect using ccw. In this question, you will give the "robust" version of that algorithm. Write an algorithm that takes two line segments as input (specified by the end points) and outputs true if the segments intersect and false otherwise. Assume that the segments are closed, so they are considered intersecting if the endpoint of one line segment lies on the other segment. This will require that you check for 0 in ccw test.