Homework 3.  Due at beginning of class, Tuesday March 25.  

1) (a) Give an O(n) time (It can be expected time) algorithm for the
following problem. You are given a set of line segments, each segment
having a black endpoint and a white endpoint. Determine whether there
is a circle that intersects all of these segments, such that the black
endpoints are inside (or on) the circle and the white endpoints are
outside (or on) the circle.



(b) Suppose that the endpoints are not colored and you simply want to
find a circle that intersects all the line segments. Can you
generalize the algorithm from part (a) to work in this case in linear
time? Either do so or explain intuitively why it seems to be difficult
to generalize.


2)  Book, Problem 6.3 (written out below):

Here we talk about the "Single Shot" problem.  We want to know if a
query point is in a polygon, but we are given the query point and the
polygon at the same time.  

Given a polygon P and a query point q, here is an algorithm to
determine if q lies in P.  Consider the ray (call it r) that shoots
straight left from q.  Determine for every edge e of P whether it
intersects r.  If the number of intersections is odd, the q is in P,
otherwise, q is not in P.

(a) Assuming no degenerate cases, prove that this algorithm is
correct.  (that is, if q is in the polygon, then this ray has an odd
number of intersections, AND if q is not in the polygon, then this ray
has an even number of intersections).

(b) Explain how to deal with degenerate cases.  One such case is when
the ray r intersects the end point of an edge.  Are there other
special cases?

(c) What is the running time of this algorithm?