Advancing front circle packing to approximate conformal strips

A circle packing is a set of tangent and disjoint discs. Maps between circle packings with the same tangency are discrete analogues of conformal mappings, which have application for example in mechanical, fluid, and thermal engineering. We describe an advancing front algorithm to compute the circle packing of a strip around a closed planar curve. Conformal mappings preserve local angles and shapes; our algorithm uses these properties to obtain via the fast Fourier transform the centers and radii for the circle packing of successive trigonometric Lagrange curves in a strip. To check the algorithm, different results are compared with well-known conformal mappings. Real time deformations of circle packings are possible by changing the shape of the initial closed curve.     

On the Density of 2-Saturated Lattice Packings of Discs

 In a recent paper of G. Fejes Tóth, G. Kuperberg and W. Kuperberg [1] a conjecture has been published concerning the greatest lower bound of the density of a 2-saturated packing of unit discs in the plane. (A packing of unit discs is said to be 2-saturated if none of the discs could be replaced by two other ones of the same size to generate a new packing. A packing of the unit disc is a lattice packing if the centers form a point lattice.) In the present note we study this problem for lattice packings, however, in a more general form in which the removed unit disc is replaced by two discs of radius r. A corollary of our results supports the above conjecture proving that a lattice packing cannot be 2-saturated except if its density is larger than the conjectured bound. (Received 6 December 2000; in revised form March 29, 2001)     

Random Sequential Adsorption of Discs on Surfaces of Constant Curvature: Plane,Sphere, Hyperboloid,and Projective Plane

We present an algorithm to simulate random sequential adsorption (random “parking”) of discs on constant curvature surfaces: the plane, sphere, hyperboloid, and projective plane, all embedded in three-dimensional space. We simulate complete parkings efficiently by explicitly calculating the boundary of the available area in which discs can park and concentrating new points in this area. We use our algorithm to study the number distribution and density of discs parked in each space, where for the plane and hyperboloid we consider two different periodic tilings each. We make several notable observations: (1) on the sphere, there is a critical disc radius such the number of discs parked is always exactly four: the random parking is deterministic. We prove this statement and also show that random parking on the surface of a d-dimensional sphere would have deterministic behaviour at the same critical radius. (2) The average number of parked discs does not always monotonically increase as the disc radius decreases: on the plane (square with periodic boundary conditions), there is an interval of decreasing radius over which the average decreases. We give a heuristic explanation for this counterintuitive finding. (3) As the disc radius shrinks to zero, the density (average fraction of area covered by parked discs) appears to converge to the same constant for all spaces, though it is always slightly larger for a sphere and slightly smaller for a hyperboloid. Therefore, for parkings on a general curved surface we would expect higher local densities in regions of positive curvature and lower local densities in regions of negative curvature.     

Note on an Inequality of Wegner

Wegner gave a geometric characterization of all so-called Groemer packing of n ≥ 2 unit discs in E ² that are densest packings of n unit discs with respect to the convex hull of the discs. In this paper we provide a number theoretic characterization of all n satisfying that such a "Wegner packing" of n unit discs exists, and show that the proportion of these n is 23/24 among all natural numbers.     

Optimized Dropping and Rolling (ODR) method for packing of poly-disperse spheres

Powder-based microstructures are traditionally modelled using densely packed spherical particles. In this letter, a new dropping and rolling packing algorithm is employed by means of analytical equations, to investigate the random packing of spherical particles. The three-dimensional randomly packed microstructures are quantified in terms of packing density and computational time.     

基于模拟退火算法的矩形优化排样问题的研究

考虑了一种矩形优化排样系统中遗传算法和模拟退火算法的结合算法.首先建立了该系统的通用数学模型.然后给出了求解该问题的遗传模拟退火算法.最后用VC++6.0模拟算例的结果表明该算法是一种行之有效的方法.     

Expandability radius versus density of a lattice packing

In the present paper lattice packings of open unit discs are considered in the Euclidean plane. Usually, efficiency of a packing is measured by its density, which in case of lattice packings is the quotient of the area of the discs and the area of the fundamental domain of the packing. In this paper another measure, the expandability radius is introduced and its relation to the density is studied. The expandability radius is the radius of the largest disc which can be used to substitute a disc of the packing without overlapping the rest of the packing. Lower and upper bounds are given for the density of a lattice packing of given expandability radius for any feasible value. The bounds are sharp and the extremal configurations are also presented. This packing problem is related to a covering problem studied by Bezdek and Kuperberg [BK97]. This revised version was published online in June 2006 with corrections to the Cover Date.     

Geometric analysis for the metropolis algorithm on Lipschitz domains

This paper gives geometric tools: comparison, Nash and Sobolev inequalities for pieces of the relevant Markov operators, that give useful bounds on rates of convergence for the Metropolis algorithm. As an example, we treat the random placement of N hard discs in the unit square, the original application of the Metropolis algorithm.     

Asymptotic packing via a branching process

It is shown that under certain side conditions the natural random greedy algorithm almost always provides an asymptotically optimal packing of disjoint hyperedges from a hypergraph H.     

Three-stage heuristic algorithm for three-dimensional irregular packing problem

This paper studies a new practical problem which can be decomposed into three three-dimensional packing problems: three-dimensional irregular packing with variable-size cartons problem, three-dimensional variable-size bin packing problem, and the single container loading problem. Since the three sub-problems are NP-hard, searching a good solution becomes more difficult. In this paper, mathematical models of each sub-problem are developed and three-stage heuristic algorithms are proposed to solve this new problem. Experiments are conducted with random instances generated by real-life case. Computational results indicate that the proposed algorithm is efficient and can yield satisfactory results.     

Quasi-human seniority-order algorithm for unequal circles packing

In the existing methods for solving unequal circles packing problems, the initial configuration is given arbitrarily or randomly, but the impact of different initial configurations for existing packing algorithm to the speed of existing packing algorithm solving unequal circles packing problems is very large. The quasi-human seniority-order algorithm proposed in this paper can generate a better initial configuration for existing packing algorithm to accelerate the speed of existing packing algorithm solving unequal circles packing problems. In experiments, the quasi-human seniority-order algorithm is applied to generate better initial configurations for quasi-physical elasticity methods to solve the unequal circles packing problems, and the experimental results show that the proposed quasi-human seniority-order algorithm can greatly improve the speed of solving the problem.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Some Densest Two-Size Disc Packings in the Plane

The main purpose of this paper is to prove some long-standing conjectures concerning the packing density of some compact arrangements of discs of two different radii in the Euclidean plane. To reach this goal a new method, called cell balancing, is presented.     

Compact Packings of the Plane with Two Sizes of Discs

We consider packings of the plane using discs of radius 1 and r. A packing is compact if every disc D is tangent to a sequence of discs D₁, D₂, ..., D_n such that D_i is tangent to D_i+1. We prove that there are only nine values of r with r < 1 for which such packings are possible. For each of the nine values we describe the possible compact packings.     

On the Use of Particle Markov Chain Monte Carlo in Parameter Estimation of Space-Time Interacting Discs

A space-time random set is defined and methods of its parameters estimation are investigated. The evolution in discrete time is described by a state-space model. The observed output is a planar union of interacting discs given by a probability density with respect to a reference Poisson process of discs. The state vector is to be estimated together with auxiliary parameters of transitions caused by a random walk. Three methods of parameters estimation are involved, first of which is the maximum likelihood estimation (MLE) for individual outputs at fixed times. In the space-time model the state vector can be estimated by the particle filter (PF), where MLE serves to the estimation of auxiliary parameters. In the present paper the aim is to compare MLE and PF with particle Markov chain Monte Carlo (PMCMC). From the group of PMCMC methods we use specially the particle marginal Metropolis-Hastings (PMMH) algorithm which updates simultaneously the state vector and the auxiliary parameters. A simulation study is presented in which all estimators are compared by means of the integrated mean square error. New data are then simulated repeatedly from the model with parameters estimated by PMMH and the fit with the original model is quantified by means of the spherical contact distribution function.     

Efficient algorithms for orthogonal packing problems

The NP complete problem of the orthogonal packing of objects of arbitrary dimension is considered in the general form. A new model for representing objects in containers is proposed that ensures the fast design of an orthogonal packing. New heuristics for the placement of orthogonal packing are proposed. A single-pass heuristic algorithm and a multimethod genetic algorithm are developed that optimize an orthogonal packing solution by increasing the packing density. Numerical experiments for two- and three-dimensional orthogonal packing problems are performed.     

Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Some of this work done at Stanford University, supported by National Science Foundation and Hertz Foundation Graduate Fellowships, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation and Xerox Corporation. Also supported by NSF award 962-4239.     

Variability reduction with multiweighing proceedings

Summary In this paper we study the variability reduction gain in the production processes that require a process of packing with the objective of sales at constant nominal weights. We have obtained the value of the percentage variability reduction index in the packing processes of units formed by a fixed number of pieces attending to random packing and multiple weighting with variable number of scaling pan packing criteria. These indexes have been obtained both for only one packing objective processe and for double objective packing processes. Collaborator in the Catalan Institute of Technology (ICT).     

约束装箱问题的混合遗传算法求解

本将最佳适应法和遗传算法相结合，提出了一种新的启发式混合遗传算法对具有时间约束的装箱问题进行求解，给出了具体的算法步骤，试算结果表明基于启发式算法的混合遗传算法适合于求解各种约束条件下的大规模装箱问题。     

Approximating the zeros of analytic functions by the exclusion algorithm

We give a practical version of the exclusion algorithm for localizing the zeros of an analytic function and in particular of a polynomial in a compact of . We extend the real exclusion algorithm to a Jordan curve and give a method which excludes discs without any zero. The result of this algorithm is a set of discs arbitrarily small which contains the zeros of the analytic function.