Abstract

This dissertation will describe the work done in determining the random packing density of disks in a two-dimensional plane. This will be achieved by developing an algorithm to simulate packing densities of disks within a plane. This project will be particularly interesting as there are applications in a wide range of scientific disciplines.

1 Chapter1-Introduction

1.1 Introduction

Disk packing is the geometrical study of the disk arrangement on a plane. In the study of hard disk packing, no overlapping of neighbouring disks occurs. The proportion of the surface covered by disks is referred to as the packing density and is dependent on the arrangement of disks. This is of interest in packing problems since it is preferable to pack as many disks as possible in the given plane. There are a diverse types of disk arrangements which contribute to packing density, as well as uniform and non-uniform disk types.

Random packings of two-dimensional disks are of great interest because they can be used to generalise models for random packing in three-dimensional shapes like cylinders and spheres. These can be used as prototype models of many real structures, e.g. chain polymers, liquid crystals, fibrous materials. These structures contribute to a wide variety of scientific research and engineering applications.

1.2 Background

There are many factors which effect the packing density of disks. This section will describe some of the major influences which contribute to packing density.

1.2.1 Arrangement

IthasbeenlongprovenbyLagrangethatthehighestdensityachievedindiskpackingisahexagonalarrangement[1].

Figure 1: Square versus Hexagonal Disk Packing[1].

However, there are infinite packing arrangements that can have long-range order or a random order. The hexagonal arrangement does not always apply as this assumes that all disks are of uniform size.

1.2.2 Disk Size

Disk sizes can be sorted into three categories:

•   Mono-diverse: each disk is of equal size.

•   Bi-diverse: disk packings of two different sizes.

•   Poly-diverse: disk packings ranging from three to infinite disk sizes.

The difficulty in determining the best packing density of disks becomes increasingly difficult as the number of disk sizes increases since a poly-diverse disk packing is less likely to have a long-range order.

1.2.3 Plane Shape

It can easily be seen that the geometry of the shape greatly influences disk packing density.

Figure 2: Figure 2 Disk Packing in Round and Square Planes (Wolfram Alpha)

Packing density in a three-dimensional plane can be calculated using the following equation:

4 r3 Volume of atoms 3π

η= Volume of unit cell = a3

The equation is dependent on the packing arrangement i.e. face centred cubic, body centred cubic etc. however, it can be seen that the packing density of three-dimensional cube is also dependent on the volume of the unit cell. This fact also holds true for two-dimensional planes, where shape, and therefore area, have an important role in determining packing fraction and density.

http://ecee.colorado.edu/ bart/ecen3320/newbook/solution/hw2s.pdf

2 Chapter2-LiteratureReview

2.1 Introduction

The objective of this literature review is to provide a synopsis of the previous ways in which the circle packing problem has been approached. Let us say now that Castillo et al. [14] and Hifi et al. [33] present a comprehensive review of the packing problem considering circular and rectangular containers. In [14] the authors present a general model for the specific case discussed providing their respective industrial application. They give solutions from their numerical experiments conducted with different global optimizer software packages. In [33] the authors give a detailed review of what they called efficient approaches for the packing problem in two and three dimensions.

In this chapter, relevant literature describing the methods for two and three-dimensional disk packing in a plane are reviewed.

Disk packing problems have a wide range of applications in many disparate areas of research. [2]. Solomon brieflydescribesit’susethemodellingofidealliquids[2], whileHinrichsendiscusesseveralpossibleapplications, from physical properties; amorphous materials, liquids and glasses; to the properties of biological systems like bacteria clusters[3].

Packing refers to filling a set of geometric shapes of fixed dimensions into an area of known size. The random packing density of disks is a geometry which takes disks of equal sizes that are obtained by compaction of a configuration that is sequential and random. Historically, equal radii packing spheres which involved a two-dimensional array was used in 1619 in the era of Kepler. Two and three-dimensional packings have been studied widely since they can serve models for various physical systems[3]. Briefly, this literature review is structured with an objective illustrating as well as explaining the geometry of random packing density of disks. Three-dimensional packing is an area of interest because it has the capability of serving as models in the molecular nature of glasses, fluids as well as amorphous materials. The macroscopic granular properties of porous and powder media have undergone modelling by sphere packings. Two-dimensional packings have been studied often as a means of as an introduction to three-dimensional problem. Two-dimensional packings are not solely used to resolve three-dimensional packings, they have also been used as models for bacterial clustering or monomolecular layers’ adsorption of large molecules on a variety of surfaces. Random geometries are also a topic of interest since various physical processes such as fluid flow involved in porous media occur in random geometry[3].Processes form random geometries, like large molecules adsorption on a surface, as well as protein distribution in cell membranes, have been evaluated extensively. The non-overlapping disks compaction process that fill a surface, as well as characterising of the geometry that is produced, is an essential area in the study of two-dimensional disks random packing [4]. Consequently, the geometry involved in the randomly dense equal sized disk packing, undergoes a configuration which lacks long-ranged order, as well as

without the presence of ordered domains local configuration [5].

2.2 Packing in One Dimension

The problems of random packing, as well as random space-filling, have been discussed in literature. The topic random packing density in one dimension has often been dubbed as “the parking problem”[2]. The parking problem is an analogy, first described by Rényi in 1958, to simplify random packing density in one dimension via cars parking on a curb to analyse random packing density. The first car, of unit length, parks on the curb.

Find Out How UKEssays.com Can Help You!
Our academic experts are ready and waiting to assist with any writing project you may have. From simple essay plans, through to full dissertations, you can guarantee we have a service perfectly matched to your needs.
View our services

Independent of the first car, a second unit length car is placed uniformly on curb. If the second car does not overlap the parked car, then it is considered parked. If it does overlap the first car, then it is discarded. The process continues until no new car may be parked, that is, a unit length is not vacant as a one-dimensional simulation in geometrical probability, the aspects of geometry do not dominate as much compared to analogues of a higher dimension [2]. Analogues of higher dimensions in conjunction with the aspects of dependent probability make a formal analyse more difficult. [5]

2.3 Packing in Two and Three Dimensions

Each one-dimensional model is linked specifically to a physical model. This is achieved by evaluating the analogue of one dimension of a two or three-dimensional model. In two and three dimensions, the model’s mathematical analysis is more problematic, despite contributions to the resolution of the random space filling in one-dimension problems. The geometry involved in the area that is to be filled, as well as the geometry of units to be randomly placed, results in more issues which fail to help resolve cases of one dimension, where intervals on a line exhibit the only manner to pack or fill the line [2]. Nonetheless, there is interest in the random packing of two and three-dimensional models since some molecular models that are proposed for liquids need further evaluation. Hard particle packing that interact only with infinite forces of repulsive pairwise on contact are useful as complex models of many-body systems since the interactions that are repulsive are a major factor in the structure’s determination. Therefore, packings of hard-particles, are largely used as non-complex granular materials’ models such as glasses, some random media and liquids. Packings of hard-particle particularly hard-sphere packings have spurred an interest within mathematicians where it has been the root of various theoretical problems[4]. The idealised model of hard-spheres, which is the only interaction of interparticle, is an infinite repulsion for particle overlapping because it enables mathematicians in being accurate about the essential jamming concept.[4]

2.4 Jamming

Jammed configurations of hard particles are of great fundamental and practical interest. The exact meaning of a

“jammed” configuration is considerably ambiguous, and the questions remain in the literature [6], collectively and locally jammed packings is closely linked to rigid and stable packings concept of mathematics. The idealised model of hard-sphere is similar to the Ising Model which is used in studying the various physical systems of hard-particle as well understanding the model. Jamming is a term that is used in granular media modelling, which consists of some effects like adhesion, particle deformability and friction. Through the definition of hard-sphere systems, these effects are not considered. Notably, the jamming of hard-sphere is conveyed from a perspective which focuses on the final packed geometry states[4]. Three broad and mathematically precise “jamming” categories of sphere packings can be distinguished depending on the nature of their mechanical stability [6][4]. In order of increasing stability, for a finite sphere packing, these are the following:

•   Local jamming: Each particle in the packing is trapped by its neighbours i.e. it cannot be translated while fixing the positions of all other particles;

•   Collective jamming: Any locally jammed configuration is collectively jammed if no subset of particles can simultaneously be displaced so that its members move out of contact with one another and with the remainder set; and

•   Strict jamming: Any collectively jammed configuration that disallows all uniform volume-nonincreasing strains of the system boundary is strictly jammed [6][4].

In these three categories, there are distinct systems are hierarchically ordered, where locally jammed is a requirement for collectively jammed and collectively jammed is a requirement for strictly jammed particles. Particle packings that are jammed randomly experimentally produced small numbers of “rattlers.” These particles are trapped between jammed neighbours but have the freedom to move within the area enclosed by these jammed neighbours[4]. There exist many important questions that are open for the hard-particle packings of the simplest type. They involve mono-disperse packings which involve perfectly smooth spheres that are impenetrable. One problem of these packings involves the classification of disordered and ordered jammed sphere packings and circular disk packings for the many jamming classifications, which are described various ways. Since an individual has no capability of computing all packings possible, even for a small number of particles, it is important to compute a small parameter’s set which can well characterise packings[4]. Two essential packing’ scalar properties are the order metric and the density. Numerical algorithms have served as primary tools used in studying quantitatively random packings.

2.5 Simulations of Packings

Two algorithms are used in evaluating packing of collectively, strictly or locally jammed hard spheres. The first algorithm focuses on packings that consist of inter-particle contacts, and the second algorithm allows for gaps that are significant inter-particle[4]. The two algorithms used are based on linear programming and are applied to ordered and disordered disk and sphere packings. Additionally, the algorithms that produce hard-particle packings in large scale are essential, especially because configurations of experimental hard-particle are hard to acquire, and their applicability is limited [7]. On the other hand, the stochastic algorithms are of specific interest since they are focused at production of disordered or random packings. Through the aid of numerical investigations, several packing algorithms have been used to produce jammed packings under appropriate conditions. The studies of bi-disperse and mono-disperse disk packings showed that there was a similar behaviour of these packings[4]. The study of the Lubachevsky – Stillinger packings aid in the arrival of several essential conclusions which find that amorphous mono-disperse and bi-disperse packings are practically strictly jammed. The second conclusion is that the large packings of the mono-disperse disks are highly crystalline and are collectively jammed only. The conclusions made show the distinctions among the different jamming types, which are essential in judging packing stability on the sole basis of local criteria. It has been suggested that locally jammed configurations are easiest to implement in a computer simulation. To determine whether each disk is locally jammed, it must be found if each disk has at least three contacting neighbours that do not all lie in a semicircle surrounding the particle of concern[6]. Computer-simulated packings are analysed such that they are never ideal and there are often small gaps between some particles. However, the jamming classification as mentioned above, are usually too specialised or restrictive during the analysis of large disordered packings that contain of bigger inter-particle gaps, where the displacement of particles may be compared to the typical size of particles[4]. Thus, where jamming can be studied, it is essential to focus on attempting to make the displacement of spheres away from their present position. Generation of random density packings have been implemented in the studies to test the occurrence of jamming in sphere packings where they are applied in mono-disperse and bi-disperse packings, based on the conditions of the periodic table. The application of the Lubachevsky – Stillinger algorithm in compression is essential when applied under the conditions of the periodic boundary [5]. The algorithm is a dynamic of the hard-sphere molecules where spheres increase in size in the simulation period at a particular rate of expansion. There are distinct results observed in studies of amorphous packings of mono-disperse spheres, the disk binary packings, as well as polycrystalline mono-disperse disk packings. The results of these packings show that they were all collectively jammed with a possibility of small or average particle displacements. Generally, the small displacements are due to the early termination or rattlers of the packing algorithm[4]. A point to note is that it is believed that a true final packing of the Lubachevsky – Stillinger algorithm consists of an infinite rate of collision will have an ideal sub-packing that is collectively jammed. Moreover, the difference between the strict and collective jamming boundary effects signifies that the packings become bigger as the boundary effects decrease. Thus, even if the packing algorithm lack to generate packings that are strictly jammed, they do this for large packings which are amorphous. It is important to note is that the results for mono-disperse packing disks were different as they tend to be almost crystalline. The crystallisation that occurs into triangular lattice brings about an obstacle of convergence for the algorithm of

Lubachevsky-Stillinger because close to the triangular areas have collision rates that are very high. [4]

2.6 Conclusions

Reviewing the recent literature on the subject of disk packing is a challenging and difficult problem with real-world applications in diverse fields of study. There are many effects which need to be addressed when attempting to compute optimum packing density. This is not a new field of study but has been more successful in recent time due to the advancement of computer science. Developing an algorithms to simulate random packing will arguably be the most important step in experimental stages of this dissertation.

3 References

[1]    Hugo Steinhaus. Mathematical snapshots. Dover Publications, 3rd edition, 1999.

[2]    Herbert Solomon. Random packing density. pages 119–134, 1967.

[3]    Einar L. Hinrichsen, Jens Feder, and Torstein Jøssang. Random packing of disks in two dimensions. Phys. Rev. A, 41:4199–4209, Apr 1990.

[4]    Aleksandar Donev, Salvatore Torquato, Frank H. Stillinger, and Robert Connelly. Jamming in hard sphere and disk packings. Journal of Applied Physics, 95(3):989–999, 2004.

[5]

[6]    Hard particle Packings, S. Torquato, and F. H. Stillinger. Multiplicity of generation, selection, and classification procedures for jammed hard-particle packings. J. Phys. Chem. B, 105:11849–11853, 2001.

[7]    Mohamed Ebeida, Scott Mitchell, Anjul Patney, Andrew Davidson, and John Owens. A simple algorithm for maximal poisson-disk sampling in high dimensions. 31:785–794, 05 2012.