=> Suppose you have 2n dots, n red and n blue.  Are you always able to
=> connect each red dot to a blue dot with a straight line so that the paths
=> never cross?

Yes, if no 3 points are collinear. This was Problem A-4 on the 1979 Putnam 
exam. Solutions were published in the American Math Monthly, and collected 
in a book edited by G L Alexanderson et al. 

Gerry Myerson (gerry@mpce.mq.edu.au)
---------------------------------------------------------------------------
Exercise 35-3 Ghostbusters and ghosts
 (Cormen, Leiserson, Rivest; Intro. to Algorithms, MIT Press, 1990)

A group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed
with a proton pack, which shoots a stream at a ghost, eradicating it. A
stream goes in a straight line and terminates when it hits the ghost. The
Ghostbusters decide upon the following strategy. They will pair of with
the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously
each Ghostbuster will shoot a stream at his or hoer choosen ghost. As we 
all know, it is very dangerous to let streams cross, and so the Ghostbusters
must choose pairings for which no streams will cross.
   Assume that the position of each Ghostbuster and each ghost is a fixed
point in the plane and that no three positions are collinear.

a. Argue that there exists a line passing through one Ghostbuster and one
   ghost such the number of Ghostbusters on one side of the line equals
   the number of ghosts on the same side. Describe how to find such a line
   in O(n log n) time.

b. Give an O(n^2 log n)-time algorithm to pair Ghostbusters with ghosts in
   such a way that no streams cross.
---------------------------------------------------------------------------
Three collinear points are not evil but four. The forbidden configuration
is:

      O--O--X--X

Torsten Sillke (Torsten.Sillke@uni-bielefeld.de)