The smallest convex \(k\)-gon containing \(n\) congruent disks (Q2674985): Difference between revisions

Let \(S\) be a set of \(n\) non-overlapping disks of radius 1 in the Euclidean plane. \(S\) is \textit{efficiently packed} if the following conditions hold: 1) the convex hull of the disk centers is either a line segment of length \(2(n-1)\) or can be triangulated into equilateral triangles of edge length 2 using the \(n\) centers as vertices; 2) the perimeter of the hull is \(2p\), where \(p\) is the smallest integer number greater than or equal to \(\sqrt{12n-3}-3\). Let \(H\) be the convex hull of \(S\). It is proved (Wegner inequality) that the area of \(H\) is greater than or equal to \(\sqrt{12}(n-1)+(2-\sqrt{3})p+\pi\), and the equality holds if and only if \(S\) is efficiently packed. The authors prove that if \(P\) is a convex \(k\)-gon containing \(S\), then the area of \(P\) is greater than or equal to \(\sqrt{12}(n-1)+(2-\sqrt{3})p+k\cdot \tan\frac{\pi}{k}\), and the equality holds for some efficiently packed sets which are precisely described in Theorem 4 of the paper. Theorem 5 presents the smallest-area convex \(k\)-gon containing \(S\) for some cases where the above inequality is tight. Theorem 6 demonstrates that some sets of disks non efficiently packed can be contained by a minimal-area polygon. The paper includes many figures that help the reader.