Contacts in totally separable packings in the plane and in high dimensions

Naszódi, Márton and Swanepoel, Konrad (2022) Contacts in totally separable packings in the plane and in high dimensions. JOURNAL OF COMPUTATIONAL GEOMETRY. pp. 471-483. ISSN 1920-180X

Preview

Text naszodi-numbered.pdf Download (497kB) | Preview

Abstract

We study the contact structure of totally separable packings of translates of a convex body K in Rd, that is, packings where any two touching bodies have a separating hyperplane that does not intersect the interior of any translate in the packing. The separable Hadwiger number Hsep(K) of K is defined to be the maximum number of translates touched by a single translate, with the maximum taken over all totally separable packings of translates of K. We show that for each d ≥ 8, there exists a smooth and strictly convex K in Rd with Hsep(K) > 2d, and asymptotically, Hsep(K) = Ω((3/√8)d). We show that Alon’s packing of Euclidean unit balls such that each translate touches at least 2d others whenever d is a power of 4, can be adapted to give a totally separable packing of translates of the l1-unit ball with the same touching property. We also consider the maximum number of touching pairs in a totally separable packing of n translates of any planar convex body K. We prove that the maximum equals ⌊2n − 2√n⌋ if and only if K is a quasi hexagon, thus completing the determination of this value for all planar convex bodies.

Actions (login required)

Edit Item