600.488 Homework Assignment 7

Draw a line segment s in the plane, and draw a representation in the dual plane of the set of all lines that intersect s.
Consider a point set S defined as follows. Place three rays emanating out from the origin, each separated from the next by an angle of 120 degrees. Place n/3 points of S to be equally spaced along each ray. How many edges are on the median level of the arrangement formed by the duals to the points in S?
Given a set S of n lines in the plane, design an O(n log n)-time algorithm for finding the convex hull of the (finite) vertices in the arrangement of the lines in S.
Given a set S of n points in the plane, design an efficient data structure that can answer line-dragging queries, where a line-draggin query is specified by giving a non-vertical line l and asking for the first point of S that would be hit by dragging l vertically upward keeping its slope the same. Shoot for a running time of O(log n) time with a data structure using O(n²) space.
Suppose you are given a set S of n lines in the plane, and a set T of n points in the plane. Design an efficient algorithm to determine if one of the points in T is on one of the lines in S. (Hint: Shoot for an algorithm running in a little more than O(n^3/2) time, which begins by dividing S into O(n^1/2) groups of size O(n^1/2) each.) Characterize as closely as possible with the big-oh notation the asymptotic running time of your algorithm?