2. (25 points) Let A(L) denote a simple arrangement of a set L of n lines. Describe an O(n log n)-time algorithm for constructing the convex hull of all intersection points.
3. (25 points) Prove that the test for collinearity of three points in a set of n points on the plane, is as hard as checking whether there exist three distinct integers a, b, c among a set of n integers, such that (a + b + c) = 0.
4. (25 points) Consider the visibility graph G(V, E) of a set of n disjoint line-segments on the plane. Assume for simplicity that no three end-points of line-segments are collinear, and no line segment is horizontal or vertical. Each end-point defines a vertex in V. An edge (v1, v2) appears in E when the two end-points corresponding to v1 and v2 either belong to the same segment, or are visible on the plane. An example of visibility graph for a set of six line-segments is shown below.
(a) Show that G admits a cycle through all vertices. (25 points)
(b) Show that G can be constructed in O(n2)-time using arrangement and duality.
