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 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(n2) 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(n3/2) time,
which begins by dividing S into
O(n1/2) groups of size
Characterize as closely as possible with the big-oh notation the
asymptotic running time of your algorithm?