On the Total Perimeter of Homothetic Convex Bodies in a Convex Container

Abstract

For two planar convex bodies, $C$ and $D$, consider a packing $S$ of $n$ positive homothets of $C$ contained in $D$. We estimate the total perimeter of the bodies in $S$, denoted $\mathrm{per}(S)$, in terms of $\mathrm{per}(D)$ and $n$. When all homothets of $C$ touch the boundary of the container $D$, we show that either $\mathrm{per}(S)=O(\log n)$ or $\mathrm{per}(S)=O(1)$, depending on how $C$ and $D$ "fit together," and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound $\mathrm{per}(S)=O(\log n)$ unless $D$ is a convex polygon and every side of $D$ is parallel to a corresponding segment on the boundary of $C$ (for short, $D$ is \emph{parallel to} $C$). When $D$ is parallel to $C$ but the homothets of $C$ may lie anywhere in $D$, we show that $\mathrm{per}(S)=O((1+\mathrm{esc}(S))\log n/\log \log n)$, where $\mathrm{esc}(S)$ denotes the total distance of the bodies in $S$ from the boundary of $D$. Apart from the constant factor, this bound is also the best possible.

arXiv commentA preliminary version of this paper appeared in Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013), Berkeley, CA, 2013, LNCS~8096, pp. 96--109

References in corpus (2)

• Approximation algorithms for TSP with neighborhoods in the plane
• On a strong version of the Kepler conjecture