600.488 Homework Assignment 7
Due: Wednesday, April 14, 1999

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 linedragging queries,
where a linedraggin query is specified by giving a nonvertical
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^{2}) 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 bigoh notation the
asymptotic running time of your algorithm?