Algorithms
It may be difficult to see how the Delaunay diagrams seen in the previous applet are unique among all the other possible choices of connections between birds. To better explain this, we will illustrate the algorithms which construct the diagram.
S-Hull
We begin by simply connecting all the birds in some triangulation. At this point, the connections need not be realistic connections connecting nearby birds.
This video illustrates the first stage of the S-Hull algorithm.1 Note that some of the line segments connect quite distant birds, we will correct this in a later step.
Periodic Boundary Conditions
In the space of our model, a bird near the left boundary can be very close to a bird near the right boundary. However, the connections constructed above do not connect these nearby birds. As a next step, we connect those birds near the boundaries using a new algorithm.2 The new edges are seen in blue in the first frame of the video below.
Edge Flipping
It is important that the provisional connections we have constructed so far do not overlap and in fact form triangles. The triangles in a Delaunay triangulation satisfy a special property illustrated in the figure at right. If the connection in red were part of a Delaunay triangulation, the sum of the angles indicated by the black birds would be greater than 180o. Note that if the red connection fails this test, the flipped connection between the blue birds must satisfy it. In fact, if we systematically flip all of the edges so that this property is satisfied we will converge to the Delaunay triangulation.
The video above illustrates the flipping algorithm. Note how in the end all of the connections - even the blue connections crossing the boundaries - connect birds (vertices) which seem to be natural neighbors. This is the sense of neighbor used in our model.
Diagram Repair
As the birds move in time the existing connections are distorted. We may continue to use the flipping algorithm to correct the interactions between birds. The edge flipping may be seen in the Delaunay view in the applet implementing the new model.
However, sometimes the birds will move so that the existing connections overlap, and the flipping algorithm is not sufficient. We use a new algorithm3 which repairs these defective connections while allowing most connections to be corrected through the flipping procedure. The algorithm was inspired by the more general Star Splaying algorithm.