| Assume that no three points lie on a straight line. [Surely the worthy
Mr Goodman didn't intend that we fiddle around with collinear sets of
points.]
Let <a,b,c> = 1 iff a,b,c are clockwise
else = -1 (iff a,b,c are anticlockwise)
Then <a,b,c> = <b,c,a> = - <a,c,b>, etc.
Consider four points, a,b,c,d. The convex hull will either be a
quadrilateral or a triangle. By examining 6+2=8 different labellings, it is
easy to see that:
<a,b,c> = majority{ <a,b,d>, <b,c,d>, <c,a,d> }
where majority{x,x,x} = majority{x,x,-x} = x, etc. You get the idea.
This means that the n-choose-3 values of <a,b,c> are determined by the
n-choose-2 values of <a,b,z> for some fixed point z.
Put z wlog at the origin, put a wlog at (1,0). Then the only variables
which remain are the angles azb.
Suppose that we have n points drawn already. These divide up the plane
into 2(n-1) segments. There are 2(n-1) different equivalence classes
possible, depending on where the n+1th point is deposited.
If F(n) is the number of equivalence classes, then
F(n) = 2*(n-2)*F(n-1).
F(2) = 1.
So:
F(n) = (n-2)! * 2^(n-2)
I'm not sure that Stan's request to draw representatives of the
equivalence classes is now very illuminating, since there is a clear
recursive construction.
Cheers,
Andy.
|