Howard Hughes Young Scholar Research Program at Beloit College

My research concentrated on studying animal territories using the Voronoi diagram to analyze the areas. I closely looked at Royal Tern's nests packing and Bark Beetles' entrance points into the bark of a tree. My hypothesis was that the territories that animals occupy at high densities will have roughly the same area. Are these areas the same? What are the factors that lead to this if they are the same? Anf if not, why? I looked at research done in this field by scientists like Grant (1968), Barlow (1974), Buckley and Buckley (1977), and Byers (1992) and studied their papers. As a part of my project I also concentrated on presenting this research to a large audience by making Web pages about the project. These Web pages can be found on http://stu.beloit.edu/~biology/zdravko/voronoi.html.

A Voronoi diagram (also known as a Dirichlet tessellation) of a set of sites (points) is a collection of regions that divide up the plane. Each region corresponds to one of the sites, and all the points in one region are closer to the corresponding site than to any other site (Erickson, 1996) (Fig. 1).

Fig. 1.1 and 1.2: Voronoi points and diagrams drawn in by using points on 1.1

The Delaunay triangulation in two dimensions consists of non overlapping triangles where no points in the network are enclosed by the circumscribing circles of any triangle. (Fig. 2) There is a very strong connection between these two terms and one can always be used for calculating the other (MidtbŻ, 1996).

Fig. 2.1 and 2.2: Delaunay triangulation based on points from the Voronoi diagram and both represented on Fig. 2.1

The concept of Voronoi diagrams first appeared in works of Descartes as early as 1644. Descartes used Voronoi-like diagrams to show the disposition of matter in the solar system and its environs. The first man who studied the Voronoi diagram as a concept was a German mathematician G. L. Dirichlet. He studied and defined the two- and three- dimensional case. After him this concept became known as a Dirichlet tessellation. However, Voronoi diagrams are used much more widely today because another German mathematician M. G. Voronoi in 1908 studied the concept and defined it for a more general n-dimensional case. Soon after it was defined by Voronoi, it was developed independently in other areas like meteorology and crystallography. Thiessen developed it in meteorology in 1911 as an aid to computing more accurate estimates of regional rainfall averages. (Okabe et al., 1992) This concept was rediscovered many times in different fields of science and today it is extensively used in about 15 different fields of sciences including mathematics, computer science, biology, cartography, physiology and many others (Erickson, 1996).

I first identified all of the points and then selected only those that could be clearly identified as entrance points. Using NIH Image 1.6 (a software program developed by Wayne Rasband, wayne@helix.nih.gov), I marked all of them and collected the coordinates of all the points (Fig. 4)

My first goal was to construct Voronoi diagrams for the entrance points so I could calculate the areas and then compare them. In order to do this I first had to identify all the Voronoi points (circumcenters) that connect and form polygons. For this reason I constructed a Delaunay triangulation connecting all the Voronoi center points (entrance points; Picture 1, appendix). After this I printed the image and used the Delaunay triangulation to construct Voronoi diagrams by hand (preciseness was not important) so I could identify all the circumcenters. After identifying all of them I used a program written in C by Giancarlo Schrementi which used the formula for establishing the circumcenter of three known points (which in this case is the corner of a Voronoi polygon, connecting point, that I was striving for). The formula is given in Figure 5.

This procedure enabled me to obtain all the coordinates I needed. I used NIH Image 1.6 to put in all the coordinates of the Voronoi diagrams, then linked all of the circumcenters, and obtained six whole Voronoi polygons (Fig. 7). My next step was to calculate the areas of these diagrams in order to compare them. I used the formula displayed in Picture 2 (appendix) to calculate all the areas of these Voronoi diagrams. All of my measurements till now were in inches but now a need arose to convert them to millimeters, to get a more accurate result. All the measurements, though, are taken from the image and there are no references as to what the real distances were. After converting all the numbers by multiplying each of them with 645.16 (therefore getting all the values in square millimeters) I added them all up and divided by six to get the average value. Then I calculated the differences between the average value and single values of areas.

I used a similar procedure with Royal Terns' nests photograph. (Fig. 6) For the centers of Voronoi diagrams I used the eggs. To be able to determine the exact spot of the center and not just guess I drew two perpendicular lines across every egg and at the point where they met I chose as the center. After this the procedure was exactly the same as in the previous, bark beetle, example.

When I entered the coordinates into the bark beetle photograph I got all the points that I needed to draw in the Voronoi diagrams. (Fig. 7) The coordinates retrieved from the photograph of the entrance points can be seen in the first and second column on Table 1 and the coordinates for the circumcenters are displayed in the third and fourth column of Table 1 (appendix). On Figure 7 all the numbers of the coordinates from Table 1 are marked- the Voronoi centers (entrance points) with black dots and numbers while the circumcenters are marked with gray dots and numbers on a white background. The results from calculation of the areas for the six Voronoi polygons (marked with black capital letters on white background) are displayed in Table 2 (appendix).

The average area was 284.9 (square mm). When compared to all the single values the result indicated that my hypothesis was highly rejected- the areas were not equal to one another. Of course I still had the second picture to analyze.

On the photograph of Royal Terns' nests I followed the same procedure, but I limited the area of analysis to one smaller area to get the best possible results. The coordinates of Voronoi centers (eggs) and circumcenters can be found in Table 3 (appendix). After I constructed Voronoi diagrams for Terns' territories I ended up with twice as many complete Voronoi polygons (those that are completely surrounded by other points), twelve, which allowed me to get even better results. The areas are indicated on Figure 8 with black capital letters.

I calculated all the areas using the formula displayed in Picture 2 (appendix) and again converted all the results into square millimeters. Again, as in the previous photograph, real measurements were not available and all the data that I used was collected directly from the image. Then I found the average value and used the formula previously mentioned. The results can be seen in Table 4 (appendix). Here too, my hypothesis was highly rejected, as all of the areas had very different area sizes.

After reading all the papers and analyzing the pictures I have found that the territories of animals tend to have circular shapes in low density populations. As the density gets higher the territories tend to slowly change into polygonal shape. (Grant, 1968; Fig. 9)

Polygons (of territories) would always be exactly the same (and packed at maximum densities, they would assume hexagonal shapes) if it wasn't for the many factors which usually prevent this from happening. These factors are topography of environment, aggressiveness of species and density. Topography of environment greatly influences the shape of these territories since it is never completely uniform and has many fluctuations. This usually prevents the territories from assuming the same shapes. The second influence is the behavior of the species, their aggressiveness to be more exact. If some individuals are more aggressive, then the shapes of the territories will fluctuate in size. In these cases we would observe a number of larger and smaller territories where the less aggressive individuals would have smaller territories. The last influence is density of the population. As the density grows, the polygons start having more sides. Pentagons and hexagons will be most numerous at high densities, with hexagon shape as the perfect packing method. (Grant, 1968; Buckley and Buckley, 1977)

My research has concluded that the areas of individual territories of animals are not equal to one another. If the territories are supposed to have the same areas at high densities, but those are not achieved, then I conclude that the three influences stated in the above paragraph have a much greater influence in determining the individual territories than it is presumed. Of course a lot more research should be done in this area to be able to come to some definite conclusions.

For the bibliography used in creating this paper as well as many other references please go to the REFERENCES page.

Picture 1: Bark beetle entrance points (gray dots) connected into a Delaunay triangulation network

Picture 2: Formula for calculating the areas of Voronoi diagrams (Source: Byers 1, 1997)

Contact: Zdravko Jeremic [jeremicz@alum.beloit.edu]

posted: 07/25/97

updated: 04/22/07