TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Tuesday, October 03, 2023

More on packing and covering with circles

Reference: Erich's packing center.

We continue from these mathoverflow pages:(1) https://mathoverflow.net/questions/455365/bounds-for-the-dispersal-problem-in-convex-regions and (2) https://mathoverflow.net/questions/455309/bounds-for-minimax-facility-location-in-a-convex-region. Thanks to Prof. Roman Karasev for his comments.

1. Basic question: Given a convex region R, to pack n circles in it such that the smallest among the circles has max radius.

It is clear from Erich's packing center that even when R is a circular disk, all the n circles in an optimal layout (see n =8, for example) need not have the same radius. Then, the natural further question is to pack n circles in R that (1) maximize the least radius and (2) maximize the total perimeter of the packed circles (studied with only sum of perimeter maximized here) OR maximize the total area of the packed circles OR maximize the total number of different radii among them.

If R is a v long and thin isosceles triangle, all circles in a layout of n circles with smallest among them having max radius seem to be of different radii.
A theorem like: "When R is a disk, for any n, there can only be at most some constant number of different radii among the disks when the least radius is maximized" would be cool.

2. To cover R with n circles such that the largest among the circles has the least possible radius.

Here I don't know any R and n such that the n covering disks that minimize the maximum radius among them could have different radii. If such an example is found, the natural questions would be to find layouts that (1) minimize the max radius among covering disks and (2) minimize the total area/perimeter of all disks OR maximize the number of different radii among them or...

0 Comments:

Post a Comment

<< Home