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

Naszódi, Márton and Swanepoel, Konrad J. (2022) Contacts in totally separable packings in the plane and in high dimensions. Journal of Computational Geometry, 13 (1). 471 - 483. ISSN 1920-180X

Text (naszodi-numbered (1)) - Published Version Available under License Creative Commons Attribution. Download (497kB)

• Author

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 translates of the packing 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 2√d others whenever d is a power of 4, can be adapted to give a totally separable packing of translates of the ℓ1-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.

Item Type:	Article
Additional Information:	© 2022 The Author(s).
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Date Deposited:	31 Oct 2022 10:24
Last Modified:	20 Sep 2025 02:17
URI:	http://eprintstest.lse.ac.uk/id/eprint/117211

Actions (login required)

View Item