VORONOI POLYHEDRA OF UNIT BALL PACKINGS WITH SMALL SURFACE AREA

In this note, first, we give a very short new proof of the theorem which yields a lower bound for the surface area of Voronoi cells of unit ball packings in E ^d and implies Rogers' upper bound for the density of unit ball packings in E ^d for all d ≥ 2. Second we sharpen locally a classical result of Gauss by finding the locally smallest surface area Voronoi cells of lattice unit ball packings in E ³. This revised version was published online in August 2006 with corrections to the Cover Date.     

Densest Packing of Equal Spheres in Hyperbolic Space

   Abstract. We propose a method to analyze the density of packings of spheres of fixed radius in the hyperbolic space of any dimension m≥ 2 , and prove that for all but countably many radii, optimally dense packings must have low symmetry.     

The regular p-gonal prism tilings and their optimal hyperball packings in the hyperbolic 3-space

Summary We investigate the regular p-gonal prism tilings (mosaics) in the hyperbolic 3-space that were classified by I. Vermes in<span lang=EN-US style='font-size:10.0pt; mso-ansi-language:EN-US'>[12]and [13]. The optimal hyperball packings of these tilings are generated by the ``inscribed hyperspheres' whose metric data can be calculated by our method -- based on the projective interpretation of the hyperbolic geometry -- by the volume formulas of J. Bolyai and R. Kellerhals, respectively. We summarize in some tables the data and the densities of the optimal hyperball packings to each prism tiling in the hyperbolic space H³.     

Orthogonal packings inPG(5, 2)

Aspread inPG(n, q) is a set of lines which partitions the point set. A packing inPG(n, q) (n odd) is a partition of the lines into spreads. Two packings ofPG(n, q) are calledorthogonal if and only if any two spreads, one from each packing, have at most one line in common. Recently, R. D. Baker has shown the existence of a pair of orthogonal packings inPG(5, 2). In this paper we enumerate all packings inPG(5, 2) having both an automorphism of order 31 and the Frobenius automorphism. We find all pairs of orthogonal packings of the above type and display a set of six mutually orthogonal packings. Previously the largest set of orthogonal packings known inPG(5, 2) was two.     

Curved Hexagonal Packings of Equal Disks in a Circle

For each k ≥ 1 and corresponding hexagonal number h(k) = 3k(k+1)+1, we introduce packings of h(k) equal disks inside a circle which we call the curved hexagonal packings. The curved hexagonal packing of 7 disks (k = 1, m(1)=1) is well known and one of the 19 disks (k = 2, m(2)=1) has been previously conjectured to be optimal. New curved hexagonal packings of 37, 61, and 91 disks (k = 3, 4, and 5, m(3)=1, m(4)=3, and m(5)=12) were the densest we obtained on a computer using a so-called ``billiards' simulation algorithm. A curved hexagonal packing pattern is invariant under a rotation. For , the density (covering fraction) of curved hexagonal packings tends to . The limit is smaller than the density of the known optimum disk packing in the infinite plane. We found disk configurations that are denser than curved hexagonal packings for 127, 169, and 217 disks (k = 6, 7, and 8). In addition to new packings for h(k) disks, we present the new packings we found for h(k)+1 and h(k)-1 disks for k up to 5, i.e., for 36, 38, 60, 62, 90, and 92 disks. The additional packings show the ``tightness' of the curved hexagonal pattern for k ≤ 5: deleting a disk does not change the optimum packing and its quality significantly, but adding a disk causes a substantial rearrangement in the optimum packing and substantially decreases the quality. Received May 15, 1995, and in revised form March 5, 1996.     

More Optimal Packings of Equal Circles in a Square

The densest packings of n equal circles in a square have been determined earlier for n ≤ 20 and for n = 25, 36 . Several of these packings have been proved with the aid of a computer. The computer-aided approach is further developed here and the range is extended to n ≤ 27 . The optimal packings are depicted. Received February 11, 1998, and in revised form December 17, 1998.     

On Large Lattice Packings of Spheres

The packing density of large lattice packings of spheres in Euclidean E ^d measured by the parametric density depends on the parameter and on the shape of the convex hull P of the sphere centers; in particular on the isoperimetric coefficient of P and on the second term in the Ehrhart polynomial of the lattice polytope P. We show in E ^d , d 2, that flat or spherelike polytopes generate less dense packings, whereas polytopes with suitably chosen large facets generate dense packings. This indicates that large lattice packings in E ³ of high parametric density may be good models for real crystals.     

An example concerning the translative kissing number of a convex body

This article presents a class of convex bodies inE ^d (d≥3) where their maximum kissing numbers in translative packings are larger than their maximum kissing numbers in lattice packings. This work was supported by the Austrian Academic Exchange Service.     

Packing up to 50 Equal Circles in a Square

The problem of maximizing the radius of n equal circles that can be packed into a given square is a well-known geometrical problem. An equivalent problem is to find the largest distance d, such that n points can be placed into the square with all mutual distances at least d. Recently, all optimal packings of at most 20 circles in a square were exactly determined. In this paper, computational methods to find good packings of more than 20 circles are discussed. The best packings found with up to 50 circles are displayed. A new packing of 49 circles settles the proof that when n is a square number, the best packing is the square lattice exactly when n≤ 36. Received April 24, 1995, and in revised form June 14, 1995.     

Penny-packings with minimal second moments

We consider the problem of packingn disks of unit diameter in the plane so as to minimize the second moment about their centroid. Our main result is an algorithm which constructs packings that are optimal among hexagonal packings. Using the algorithm, we prove that, except forn=212, then-point packings obtained by Graham and Sloane [1] are optimal among hexagonal packings. We also prove a result that makes precise the intuition that the greedy algorithm of Graham and Sloane produces approximately circular packings.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Finite and Uniform Stability of Sphere Packings

The main purpose of this paper is to discuss how firm or steady certain known ball packing are, thinking of them as structures. This is closely related to the property of being locally maximally dense. Among other things we show that many of the usual best-known candidates, for the most dense packings with congruent spherical balls, have the property of being uniformly stable, i.e., for a sufficiently small ε > 0 every finite rearrangement of the balls of this packing, where no ball is moved more than ε , is the identity rearrangement. For example, the lattice packings D _d and A _d for d ≥ 3 in E ^d are all uniformly stable. The methods developed here can work for many other packings as well. We also give a construction to show that the densest cubic lattice ball packing in E ^d for d ≥ 2 is not uniformly stable. A packing of balls is called finitely stable if any finite subfamily of the packing is fixed by its neighbors. If a packing is uniformly stable, then it is finitely stable. On the other hand, the cubic lattice packings mentioned above, which are not uniformly stable, are nevertheless finitely stable. Received April 22, 1996, and in revised form October 11, 1996.     

Penny-packing and two-dimensional codes

We consider the problem of packingn equal circles (i.e., pennies) in the plane so as to minimize the second momentU about their centroid. These packings are also minimal-energy two-dimensional codes. Adding one penny at a time according to the greedy algorithm produces a unique sequence of packings for the first 75 pennies, and appears to produce optimal packings for infinitely many values ofn. Several other conjectures are proposed, and a table is given of the best packings known forn500. For largen, U3n ²/(4).     

ON THE MINIMUM INTRINSIC 1-VOLUME OF VORONOI CELLS IN LATTICE UNIT SPHERE PACKINGS

A typical 3-dimensional (in short '3D') Voronoi cell of a 3Dlattice has six families of parallel edges. We call any six representants of these six families the generating edges of the Voronoi cell. The sum s of lengths of generating edges of a Voronoi-cell of a lattice unit sphere packing in the 3-dimensional Euclidean space is a special case of intrinsic 1-volumes of 3Dzonotopes with inradius 1 which are investigated accurately in [B]. However, the minimum of this value is unknown even in this special case. As the regular rhombic dodecahedron shows optimal properties in many similar problems, it was reasonable to conjecture that it also has the minimal s value. In this note we present a construction of a lattice unit ball packing whose Voronoi cell possesses an intrinsic 1-volume strictly less than the one of the proper regular rhombic dodecahedron, hence providing a smaller upper bound for s than it was conjectured. A further issue of the note is a formula for edge-lengths of Voronoi cells of lattice unit ball packings that can be used efficiently in similar calculations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Densest packings of eleven congruent circles in a circle

In 1969 Pirl provided the densest packings ofn equal circles in a circle forn 10. We will prove the optimality for the packings that were conjectured forn=11. The proof is based on elementary combinatorial and analytical techniques.     

Some basic properties of packing and covering constants

This article concerns packings and coverings that are formed by the application of rigid motions to the members of a given collectionK of convex bodies. There are two possibilities to construct such packings and coverings: One may permit that the convex bodies fromK are used repeatedly, or one may require that these bodies should be used at most once. In each case one can define the packing and covering constants ofK as, respectively, the least upper bound and the greatest lower bound of the densities of all such packings and coverings. Three theorems are proved. First it is shown that there exist always packings and coverings whose densities are equal to the corresponding packing and covering constants. Then, a quantitative continuity theorem is proved which shows in particular that the packing and covering constants depend, in a certain sense, continuously onK. Finally, a kind of a transference theorem is proved, which enables one to evaluate the packing and covering constants when no repetitions are allowed from the case when repetitions are permitted. Furthermore, various consequences of these theorems are discussed.Supported by National Science Foundation Research Grant DMS 8300825.     

Highly saturated packings and reduced coverings

We introduce and study certain notions which might serve as substitutes for maximum density packings and minimum density coverings. A body is a compact connected set which is the closure of its interior. A packingP with congruent replicas of a bodyK isn-saturated if non–1 members of it can be replaced withn replicas ofK, and it is completely saturated if it isn-saturated for eachn1. Similarly, a coveringC with congruent replicas of a bodyK isn-reduced if non members of it can be replaced byn–1 replicas ofK without uncovering a portion of the space, and its is completely reduced if it isn-reduced for eachn1. We prove that every bodyK ind-dimensional Euclidean or hyperbolic space admits both ann-saturated packing and ann-reduced covering with replicas ofK. Under some assumptions onKE ^d (somewhat weaker than convexity), we prove the existence of completely saturated packings and completely reduced coverings, but in general, the problem of existence of completely saturated packings, and completely reduced coverings remains unsolved. Also, we investigate some problems related to the the densities ofn-saturated packings andn-reduced coverings. Among other things, we prove that there exists an upper bound for the density of ad+2-reduced covering ofE ^d with congruent balls, and we produce some density bounds for then-saturated packings andn-reduced coverings of the plane with congruent circles.     

Densest Packings of More than Three d -Spheres Are Nonplanar

We prove that for a densest packing of more than three d -balls, d \geq 3 , where the density is measured by parametric density, the convex hull of their centers is either linear (a sausage) or at least three-dimensional. This is also true for restrictions to lattice packings. These results support the general conjecture that densest sphere packings have extreme dimensions. The proofs require a Lagrange-type theorem from number theory and Minkowski's theory of mixed volumes. Received November 27, 1998, and in revised form January 4, 1999. Online publication May 16, 2000.     

On Extremal Finite Packings

Abstract. We show that in contrast to the classical infinite packing problem, even in the Euclidian plane, the solutions to several finite packing problems are non-lattice packings if the number of translates is large enough. This answers, in particular, a question by Paul Erdos [E].     

<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-norm packings from function fields

In this paper, we study some packings in a cube, namely, how to pack n points in a cube so as to maximize the minimal distance. The distance is induced by the L₁-norm which is analogous to the Hamming distance in coding theory. Two constructions with reasonable parameters are obtained, by using some results from a function field including divisor class group, narrow ray class group, and so on. We also present some asymptotic results of the two packings.