The Shape of Coincidence

Two discrete independent events A and B occur during the time interval 
t = 0 to T.  We can represent their joint occurrence by a point in a 
TxT square, where one axis is the time of occurrence of event A and 
the other is the time of occurrence of event B.  The region of this 
square that represents the cases in which A and B occurred within d 
of each other is the region surrounding the diagonal, as shown below.

               

Disregarding the "clipping" at the boundaries, this "region of 
coincidence" (within +-d of the diagonal) is simply the region swept 
out by a line segment of length d*sqrt(2) normal to the main diagonal.  
Therefore, we say the cross-section of the region of coincidences of 
degree d is a simple line segment of length d*sqrt(2).  We will call 
this the "shape" of 2D coincidences.

Coincidences of degree d between THREE events can be represented by 
the region near the main diagonal of a TxTxT cube.  The region of 
coincidences is swept out by a regular hexagon normal to the main 
diagonal, so the "shape" of a three-event coincidence is a hexagon, 
with edge length d*sqrt(2/3).  

In general, given a unit "cube" in n dimensions with n orthogonal
coordinates X1, X2, ...,Xn, we can consider the region of the cube's
content ("volume") consisting of points with coordinates [x1,x2,...,xn]
such that 
            |xi - xj| < q           for all i,j              (2)

This can be viewed as the region swept out by a particular n-1
dimensional object as it translates along the diagonal of the unit 
cube.  Since the solid is in the (n-1)-dimensional "plane" normal to
the diagonal, the coordinates of the solid when it is located at the
origin satisfy
                   x1 + x2 + ... + xn  =  0                    (3)

I believe the "volume" of this object is sqrt(n) q^(n-1), although I 
have proven it only for the cases n= 2, 3, and 4.

The n-1 dimensional locus satisfying (2) and (3) can be determined 
geometrically by considering the vertices.  Condition (2) for any 
i,j with i!=j implies an n-2 dimensional "face" of the convex poly-
tope, and the absolute value allows two opposite faces for each 
such i,j.  Thus, the figure has n(n-1) faces.  It can also be shown
that the number of vertices for the general n-dimensional case 
is 2^n - 2.

Points that lie on more than one face are considered to be on an 
"edge", and points that are on a maximal number of faces (meaning 
there is no path from such a point to any other face without leaving 
one of the faces it is already on) are the vertices of the polytope.  
The convexity of the polytope with these vertices is easy to see.

As an example, the six verticies of the sweeping object in the n=3 
case can be expressed in terms of multiples of q/n as follows:

	      [2,-1,-1]       [-2,1,1]
	      [-1,2,-1]       [1,-2,1]
	      [-1,-1,2]       [1,1,-2]

By rotating these points into a single 2d plane we arrive at the 
regular hexagon.  Similarly for the case n=4, the fourteen vertices
correspond to

	      [3,-1,-1,-1]      [-3,1,1,1]
	      [-1,3,-1,-1]      [1,-3,1,1]
	      [-1,-1,3,-1]      [1,1,-3,1]
	      [-1,-1,-1,3]      [1,1,1,-3]
	      [2,2,-2,-2]       [-2,-2,2,2]
	      [2,-2,2,-2]       [-2,2,-2,2]
	      [2,-2,-2,2]       [-2,2,2,-2]

These fourteen verticies can be rotated into a 3d space, showing that
they form the vertices of a solid with 12 identical diamond-shaped
faces.  One way of visualizing this solid is to begin with a unit 3d 
cube and construct an "Egyptian" pyramid on each face such that the 
faces of the adjascent pyramids are flush.  The volume of this solid 
is 2q^3.

               

This 12-faced solid is known as Kepler's Rhombic Dodecahedron.  This
fascinating shape has many interesting properties in addition to being
the "shape of coincidence" for four events.  If your browser supports
Java applets, you can see an animated view of this polyhedron by 
clicking here.

It's interesting that this solid can be said to "duplicate the cube",
reminiscent of the classical Greek problem of constructing a cube with 
twice the volume of a given cube.  This volume also appears as the
correction term in the case n=3.  Note that dimensions 3 and 4 are 
the only two dimensions for which the correction term for one is the 
sweeping volume for the other.