Homework 3.  Partial Solutions.

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.





ANSWER:  The most common answer was:

  (a) run the minimum enclosing disk algorithm to find the smallest 
disk that surroud the black points.
  (b) if that disk encloses no white points, output it
      else output fail.

This was wrong.  there are sets of segments where there is SOME
circle that includes all black points, none of the white points, 
but the SMALLEST disk surrounding the black points contains some white
points.  (Now that you know this, can you find an example?).

The right answer was to MODIFY the Minimum Enclosing Disk algorithm.

Our new algorithm gets a set of points and for each point a color, 
black and white.

Lets now DEFINE, P to be the set of points and their colors, 

Lets DEFINE the work "in" to mean inside if the point is black and
outside if the point is white.

Lets DEFINE the word "enclosing" to mean: IF the point is black, it must
lie inside (or on) the circle.  If the point it white, it must lie
OUTSIDE (or on) the circle.  

At the very end, we can "nudge" the circle so that the black point are
REALLY inside and the white points are REALLY outside.

Finally, we ignore the fact that there are segments, and just use
the set of black and white points.


okDisk(P ) :
(1) If |P | <= 3, then return the disk passing through these points.

(2) Otherwise, randomly permute the points in P . Let D(2) be the
a disk enclosing {p1, p2}

(3) for i = 3 to |P| do
  (a) if p(i) in D(i-1) then D(i) = D(i-1).
  (b) else D(i) = okDiskWith1Pt(P [1..(i - 1)], p(i) ).

okDiskWith1Pt(P;q) :

(1) Randomly permute the points in P . Let D(1) be the minimum disk
     enclosing {q, p(1)}.
(2) for i = 2 to |P| do
  (a) if p(i) in D(i-1) then D(i) = D(i-1).
  (b) else D(i) = okDiskWith2Pts(P [1..(i - 1)], q,p(i) ).

okDiskWith2Pts(P,q1,q2) :

(1) Randomly permute the points in P . Let D(1) be the minimum disk
     enclosing {q1,q2}.
(2) for i = 1 to |P| do
  (a) if p(i) in D(i-1) then D(i) = D(i-1).
  (b) else D(i) = disk(q1,q2,p(i)).

Ha!  I think this works.  If you can give me an example where this
doesn't, you can get 2 points worth of exam 1 credit.

There is also a really nice solution based upon projecting points
up onto the parabaloid.


(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.



Algorithm in part (a) exlicitly uses the knowledge of whether a 
specific point is inside or outside the circle.  The constraint that
the circle must SEPERATE two points is much less clear than the 
constraint the the circle must include one point and not another.

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).


There is an easy (informal) and a hard (but formal) proof of this.
The easy proof goes something like:

Every time the ray crosses an edge of the polygon, it changes whether
it is inside or outside.  Suppose the ray NEVER intersects the
polygon, then q must be outside.  Suppose the ray ONCE intersects the
polygon, then the ray must be inside.  


(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?

Cases:

1) ray goes from inside the polygon to outside the polygon, crossing at a
segment endpoint.  If the ray crosses a corder of two segments, but
one segment is on the left of the ray and the other segment is on the
right of the ray, then this counts as ONE intersection.

2) ray cross a "spike" of the polygon --- touching a corner joining
two segments.  If both segments are on the same side of the ray, this
counts as ZERO or TWO intersections.

3) ray goes ALONG an edge of the polygon.  Mostly we have defined the
EDGE of a polygon this year to be OUTSIDE the polygon.  So if a ray is
parallel to a segment, then we do not count this as an intersection.
However, if a ray goes along a segment, then it also touches the
endpoints of two other segments.  We want to treat this case as if
those two other segments met, and use case (1) or (2) as appropriate.

4) point q is on an edge of the polygon.  Mostly we have defined the
EDGE of a polygon this year to be OUTSIDE the polygon.  So this point
is not in the polygon. (regardless of the number of intersections you find.).



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


O(n)