On the convergence of inhomogeneous Markov chains: Approximating equilibrium placements of flexible objects

This paper deals with the minimization of local forces in two-dimensional placements of flexible objects within rigid boundaries. The objects are disks of the same size but, in general, of different materials. Potential applications include the design of new amorphous polymeric and related granular materials as well as the design of package cushioning systems. The problem is considered on a grid structure with a fixed step size w and for a fixed diameter of the discs, i.e., the number of placed disks may increase as the size of the placement region increases. The near-equilibrium configurations have to be calculated from uniformly distributed random initial placements. The final arrangements of disks must ensure that any particular object is deformed only within the limits of elasticity of the material. The main result concerns -approximations of the probability distribution on the set of equilibrium placements. Under a natural assumption about the configuration space, we prove that a run-time of n+logO(1)(1/} is sufficient to approach with probability 1 – the minimum value of the objective function, where depends on the maximum of the escape depth of local minima within the underlying energy landscape. The result is derived from a careful analysis of the interaction among probabilities assigned to configurations from adjacent distance levels to minimum placements. The overall approach for estimating the convergence rate is relatively independent of the particular placement problem and can be applied to various optimization problems with similar properties of the associated landscape of the objective function.