×

Why hard disks pack easier. (English) Zbl 0922.68005

Freivalds, Rūsiņš (ed.), Randomized algorithms. Proceedings of the international workshop, Brno, Czech Republic, August 27–28, 1998. Trier: Electronic Colloquium on Computational Complexity (ECCC), Lecture Notes Series of ECCC. (1998).
Summary: Two methods for generating dense disk packings inside 2D containers are compared in their efficiency. Both methods simulate a dynamic system of moving disks with disks being subject to a repulsion force potential. Depending on the form of the potential, the disks are treated as hard particles in one method, or soft ones in the other. Whereas the simulated trajectory of disk configuration is formally deterministic in both methods, it is argued that under the hard disk potential, the trajectory is ergodic as if the disk motion was random, which creates an advantage over the truly deterministic method under the soft disk potential. The hard disk method is experimentally shown to be able to discern a delicate distinction of the global optimum from multiple close-by local optima whereas the soft disk method usually gets stuck when the global optimum is hidden among multiple local optima.
For the entire collection see [Zbl 0911.00046].

MSC:

68M07 Mathematical problems of computer architecture
68M99 Computer system organization
Full Text: Link