Back to July Calendar 

Previous Entry Next Entry→

August 24, 2005

The next part of solving the probability problem I set out a week or so ago is proving to be cantankerously obstreperous.  The problem, to be sure, is, given a random set of 3 vertices in a unit square, what are the areas of shadow polygons, by which I mean the polygonal regions outside the triangle where a fourth vertex would not complete a convex quadrilateral. 

I thought mebbe one could use information about how the edge points are distributed around the perimeter of the unit square to determine what sort of polygonal shadows occur, but, as the diagram here show, that doesn't seem likely.

The numbers below each square indicate the distribution of edge vertices, starting with the left side and going around clockwise.  This is only a small sampling of the possibilities, of course, but it shows some of the potential complexity. Notice that the two 3-3-0-0 entries have quite different shadow polygons: the first has two triangles and a quadrilateral and the other, two triangles and a hexagon.

How about a simpler sub-problem?  How many ways are there to draw two line segments intersecting on the interior of a square?  Two configurations will only be considered different if one cannot be obtained from the other by

  1. Sliding vertices along an edge (but not to a new edge.)

  2. Rotating and/or flipping the square.

There are 5 different ways that I can find (shown at right.)  This is equivalent to saying how many ways are there to write 4 numbers, each 0, 1 or 2, whose sum is 4.  Two such sequences are different only if one can't be obtained from the other by "rotating" or reversing the sequence. 

We can list all 9 possible arrangements of edge points around the perimeter like so:
  3  |  3  |  3  |  3  |  3  |  3  |  2  |  2  |  2
 0 3 | 1 2 | 1 1 | 0 2 | 0 1 | 0 0 | 2 2 | 1 2 | 1 1
  0  |  0  |  1  |  1  |  2  |  3  |  0  |  1  |  2

For each we'd like to know how many different shadow polygon outcomes are possible.  For instance, for the first (3-3-0-0) we have two, as described above.  For 3-2-1-0, as shown below, there are either 3-gon, 4-gon, 4-gon (red) shadowgons, or 3-gon, 3-gon and 5-gon shadowgons.   When compared with 3-3-0-0 pair, I have a way of saying which is which: is the intersection of 1st and 3rd edges(counting x1, x2, x3 from left to right) above or below the line emanating from the 2nd left edgepoint?

3-1-2-0 is obtained from  3-2-1-0 by moving the right-most vertex on the top edge further right and down around the upper right corner, so it's situation is pretty much the same as 3-2-1-0.  

Truth be told, after making all these diagrams, I'm pretty tired of the nitty gritty.  Maybe I'll come back to this with a fresh mind later on.  For now, the tedium of this makes me think moving on to parsing would be a good thing.