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$
3
  • $\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$ May 1, 2022 at 4:27
  • $\begingroup$ Can the disks overlap? Or does "packing" imply that they don't? $\endgroup$ Aug 29, 2022 at 14:05
  • $\begingroup$ no, they are not allowed to overlap $\endgroup$ Aug 29, 2022 at 16:18

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$ Mar 29, 2020 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.