1
$\begingroup$

Inspired by current regulations regarding the minimal distance to be kept among people to prevent spreading of the COVID-19 virus and the maximal number of people in a group that is not subjected to that distance-regulation, I'd like to ask the following:

given

  • a minimal distance $R\ \gt\ 0$ to be kept between individuals in a "group"
  • a maximal number $k$ of individuals that are not subjected to the minimal-distance rule for groups, i.e. for each individual there are maximally $k-1$ others that are closer than $R$.

Modeling the individuals as unit circles leads to the

Question:
how many unit disks can be maximally packed in a square with sidelength $a=n*R$ under the constraint that for each disk the distance of the $k$-th nearest disk is at least $R$.

$\endgroup$
4
  • $\begingroup$ Can one ever do better than just taking the best solution for $k=1$ and replace each disk by $k$ copies of that disk? $\endgroup$ Commented May 1, 2022 at 4:27
  • $\begingroup$ Can the disks overlap? Or does "packing" imply that they don't? $\endgroup$ Commented Aug 29, 2022 at 14:05
  • $\begingroup$ no, they are not allowed to overlap $\endgroup$ Commented Aug 29, 2022 at 16:18
  • $\begingroup$ Bumped by Community Bot every four months since April of 2020. $\endgroup$ Commented Apr 20 at 22:26

1 Answer 1

0
$\begingroup$

This is an initial idea for an approximate solution for finding the densest safe packing of an infinite set of disks in the euclidean plane:

  • determine the smallest regular hexagon in which $k$ unit circles can be packed, for small $k$ known solutions can be found here and let $\varrho$ denote the radius of that hexagon's incircle

  • place copies of that hexagon at each vertex of a triangular grid with edge-lengths equal to $2\varrho+R$ and rotated to render the hexagon's sides orthogonal to the grid's edges.

  • exploit potential for further improvements by convoluting the unit disks inside the hexagons with open disks of radius $\frac{R}{2}$ and checking whether the distance of gridlines can be reduced without generating an overlap of convoluted circles in different hexagons.

$\endgroup$
1
  • $\begingroup$ I posted this as an answer to make visible that there are ideas for a solution. Please feel free to let me know if you think it isn't appropriate. $\endgroup$ Commented Mar 29, 2020 at 14:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .