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.     

Packings of Unequal Circles in a Convex Set

   Abstract. In the Euclidean plane let T be a convex set, and let K ₁ , ..., K _n be a family of n ≥ 2 circles packed into T . We show that the density of each such packing is smaller than

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.     

Covering a Rectangle With Equal Circles

Recently, Tarnai and Gáspár [22] used mechanically inspired computer simulations to construct thin coverings of a square with up to ten equal circles. We generalise the problem to rectangles and determine the thinnest coverings of a general rectangle with up to five equal circles. Partial results are presented for coverings with seven circles.     

Improved Dense Packings of Congruent Squares in a Square

Let s_n be the side of the smallest square into which it is possible to pack n congruent squares. In this paper we link s_n to the supremum of the maximal inflation Ω (C) of admissible configurations C. The computation and the properties of Ω in a bounded domain. We improve the best known packings of n equal squares for n=11, 29 and 37, and give an alternative optimal packing of 18 squares.     

Lattices of Optimal Finite Lattice Packings

We consider finite lattice ball packings with respect to parametric density and show that densest packings are attained in critical lattices if the number of translates and the density parameter are sufficiently large. A corresponding result is not valid for general centrally symmetric convex bodies.     

Lattices of Optimal Finite Lattice Packings

We consider finite lattice ball packings with respect to parametric density and show that densest packings are attained in critical lattices if the number of translates and the density parameter are sufficiently large. A corresponding result is not valid for general centrally symmetric convex bodies.The second author was partially supported by a DAAD Postdoc fellowship and the hospitality of Peking University during his work.     

A Family of Optimal Packings in Grassmannian Manifolds

A remarkable coincidence has led to the discovery of a family of packings of -dimensional subspaces of m-dimensional space, whenever m is a power of 2. These packings meet the orthoplex bound and are therefore optimal.     

求解等圆Packing问题的完全拟物算法

沿着拟物的思路进一步研究了具有NP难度的等圆Packing问题.提出了两个拟物策略,第一个是拟物下降算法,第二是让诸圆饼在某种物理定律下做剧烈运动.结合这两个策略,提出了一个统一的拟物算法.当使用N(N=1,2,3,…,100)等圆最紧布局的国际记录对此算法进行检验时,发现对于N=66,67,70,71,77,89这6个算例,本算法找到了比当前国际纪录更优的布局.     

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.     

简单平均法预测误差平方和的进一步研究

用数学归纳法对简单平均法与简单加权平均法的预测误差平方和的上界进行了比较,对简单平均法的有效性进行了分析.与相关文献的证明方法相比较,本文所采用的方法简单,直观而易懂.同时也得到了简单平均法就是最优组合预测方法的几个等价条件.     

Optimal Covering of Plane Domains by Circles Via Hyperbolic Smoothing

We consider the problem of optimally covering plane domains by a given number of circles. The mathematical modeling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. In order to overcome these difficulties, we have developed a smoothing strategy using a special class C^∞ smoothing function. The final solution is obtained by solving a sequence of differentiable subproblems which gradually approach the original problem. The use of this technique, called Hyperbolic Smoothing, allows the main difficulties presented by the original problem to be overcome. A simplified algorithm containing only the essential of the method is presented. For the purpose of illustrating both the actual working and the potentialities of the method, a set of computational results is presented.     

相同装卸工情况下装卸工问题的最优解

装卸工问题是一个新的NP困难的组合最优化问题,寻找其性能优良的近似算法是有重要的理论意义和实用价值的.相同装卸工情况下装卸工问题的系数矩阵是全么模矩阵,利用全么模矩阵的性质可以证明这种情况下的装卸工问题是多项式可解的.然而用全么模阵的性质还不能得到解的表达式.对这种情况下一辆货车的装卸工问题,用对偶单纯形法可得到最优解和最优值的解析表达式,从而可以把这个可解问题的最优值作为一般装卸工问题的近似值.这对于分析近似算法的性态是非常重要的.     

Singular Links of Two Circles and a Wedge of Circles in the 3-Sphere

A homotopy classification of singular links of two circles and a wedge of circles in the 3-sphere is given. This result generalizes Milnor's one on homotopy classification of classical three-component links. Bibliography: 3 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 299, 2003, pp. 295–299.     

Generalized Balanced Tournament Packings and Optimal Equitable Symbol Weight Codes for Power Line Communications

Generalized balanced tournament packings (GBTPs) extend the concept of generalized balanced tournament designs introduced by Lamken and Vanstone (1989). In this paper, we establish the connection between GBTPs and a class of codes called equitable symbol weight codes (ESWCs). The latter were recently demonstrated to optimize the performance against narrowband noise in a general coded modulation scheme for power line communications. By constructing classes of GBTPs, we establish infinite families of optimal ESWCs with code lengths greater than alphabet size and whose narrowband noise error‐correcting capability to code length ratios do not diminish to zero as the length grows.     

Finite Packings of Spheres

We show that the sausage conjecture of László Fejes Tóth on finite sphere packings is true in dimension 42 and above. Received October 19, 1995, and in revised form May 28, 1996.     

More on the Problem and the Solution of the Optimal Shape of a Javelin

The analogy between the optimal javelin problem and the problem of determining the optimal shape of the free rotating rod has been established and employed to determine the optimal shape of the javelin via Pontryagin's maximum principle. Five distinct variational principles are constructed for boundary value problem describing optimal shape of the javelin. The first integral for this nonlinear system is found. An a priori estimate of the cross-sectional area is obtained. The optimal shape of the javelin or free rotating rod is determined by numerical integration.