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

Joonghyun Ryu, Mokwon Lee, Donguk Kim, Josef Kallrath, Kokichi Sugihara and Deok-Soo Kim

Applied Mathematics and Computation, 2020, vol. 375, issue C

Abstract: 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).

Keywords: Tessellation; NP-hard; Heuristic; Optimization; Computational geometry; Monotone convergence (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630032030045X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:375:y:2020:i:c:s009630032030045x

DOI: 10.1016/j.amc.2020.125076

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().