OPTIMAL PLACEMENTS OF FLEXIBLE OBJECTS .2. A SIMULATED ANNEALING APPROACH FOR THE BOUNDED CASE

This paper is a continuation of the first part, where we considered re gular arrangements of flexible objects for the unbounded case. The pre sent part deals with a simulated annealing algorithm maximizing the nu mber of flexible objects in equilibrium placements within rigid bounda ries. The forces caused by the boundary are taken into account, i.e., the bounded case of placements is considered. The simulated annealing procedure makes use of the special structure of the underlying configu ration space and relationships between deformations of flexible object s and resulting forces. This allows us to obtain tight bounds for the n(3/2).ln(5/2)n and n.ln(2)n time bounds, respectively, for the comput ation of equilibrium states by annealing parameters which result in n two different cooling schedules. The deformation/force formula is deri ved from a physical model of flexible discs and is based on numerical experiments which were performed for different materials and different sizes of objects. The algorithm was first implemented and tested for the unbounded case. The run-time is relatively short, even for large n umbers of placed discs. These results are compared to the analytical o nes obtained for regular placements in the first part of the paper, an d agreement between these two sets of results are observed. Furthermor e, several experiments for placements with boundary conditions were ca rried out and the resulting placements clearly show the effect of the forces from the rigid boundary. The specialized and provably efficient simulated annealing algorithm proposed in this paper is therefore a v ery effective tool for computing equilibrium states of placements and hence useful for the design of new amorphous polymeric materials and p ackage cushioning systems as mentioned in Part I of this paper.