VOROPACK-D: Real-time disk packing algorithm using Voronoi diagram

摘要

The disk packing problem (DPP) is to find an arrangement of circular disks within the smallest possible container without any overlap. We discuss a DPP for polysized disks in a circular container. DPP is known NP-hard and reported algorithms are slow for finding good solutions even with the problem instances of small to moderate sizes. Here we introduce a heuristic algorithm which finds sufficiently good solutions in realtime for small to moderate-sized problem instances and in pseudo-realtime for large problem instances. The proposed algorithm, VOROPACK-D, takes advantage of the spatial reasoning property of Voronoi diagram and finds an approximate solution of DPP in O(nlog n) time with O(n) memory by making incremental placement of n disks in the order of non-increasing disk size, thus called a big-disk-first method. The location of a placement is determined using the Voronoi diagram of already-placed disks. If needed, we further enhance a big-disk-first realtime packing solution using the Shrink-and-Shake algorithm by taking an additional O(Mn2) time for each shrinkage where M ≪ n is the number of protruding disks for each shrinkage. Experimental results show that the proposed algorithm is faster than other reported ones by several orders of magnitude, particularly for large problem instances. Theoretical observations are verified and validated by a thorough experiment. This study suggests that Voronoi diagram might be useful for solving other hard optimization problems related with empty spaces. VOROPACK-D is freely available at Voronoi Diagram Research Center (http://voronoi.hanyang.ac.kr/software/voropack-d).