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

摘要

For two 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 per(S), in terms of n. When all homothets of C touch the boundary of the container D, we show that either per(S) = O(log n) or 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 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 parallel to C). When D is parallel to C but the homothets of C may lie anywhere in D, we show that per(S) = O((1+esc(S))log n/log log n), where 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.