1
$\begingroup$

Question: Are there planar convex regions $R$ and integers $n$ with the property: if $R$ is covered by $n$ disks of possibly different sizes such that (1) the total area of the covering disks is minimized and (2) the sum of the perimeters of the covering disks is minimized, the two resulting layouts are different?

Remarks: It is an open problem (https://en.wikipedia.org/wiki/Malfatti_circles) to find an algorithm that optimally packs $n$ disks in even a general triangle. I don't know the status of covering. But the present post is more on constructing an $R$ for which the 2 optimal covering layouts are provably different - a possibly related question on packing is here: On cutting disks from planar regions.

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer is yes.

Indeed, let $R$ be the convex hull of the set $\{A,B,C\}$, where $A:=(-1,0)$, $B:=(1,0)$, and $C:=(0,h)$, where $h\in(0,1)$. Let $n=2$. Let $D_1$ and $D_2$ be two closed disks, of respective radii $r_1$ and $r_2$, such that $R\subseteq D_1\cup D_2$.

The intersections $D_1\cap AB$ and $D_2\cap AB$ of $D_1$ and $D_2$ with the segment $AB$ are closed intervals of length $l_1\le2r_1$ and $l_2\le2r_2$ such that $l_1+l_2\ge2$. So, $r_1+r_2\ge l_1/2+l_2/2\ge1$.

Moreover, $r_1+r_2>1$ if at least one of inequalities $l_1\le2r_1$, $l_2\le2r_2$, $l_1+l_2\ge2$ is strict. The inequality $l_1\le2r_1$ will be strict if $D_1\cap AB$ is not a diameter of $D_1$. Similarly, the inequality $l_2\le2r_2$ will be strict if $D_2\cap AB$ is not a diameter of $D_2$. Also, the inequality $l_1+l_2\ge2$ will be strict if $D_1\cap AB$ is a diameter of $D_1$, $D_2\cap AB$ is a diameter of $D_1$, and the interiors of $D_1$ and $D_2$ are not disjoint.

So, $r_1+r_2>1$ unless $D_1\cap AB$ is a diameter of $D_1$, $D_2\cap AB$ is a diameter of $D_1$, and the interiors of $D_1$ and $D_2$ are disjoint. But, if the latter three conditions hold, then $R\not\subseteq D_1\cup D_2$ unless $r_1=0$ or $r_2=0$, as illustrated in the following picture (with $h=1/2$):

enter image description here

On the other hand, if one of the disks $D_1$ and $D_2$ is of radius $0$ and the other one is of radius $1$ and centered at $(0,0)$, then $R\subseteq D_1\cup D_2$. So, the smallest sum $r_1+r_2$ of the radii of closed disks $D_1$ and $D_2$ covering $R$ is $1$, and hence the smallest sum of the perimeters of closed disks $D_1$ and $D_2$ such that $R\subseteq D_1\cup D_2$ is $2\pi\times1$, and such a sum is attained if only if one of the disks $D_1$ and $D_2$ is of radius $0$ and the other one is of radius $1$ and centered at $(0,0)$.

On the other hand, if $d_1$ and $d_2$ are the closed disks such that the segments $AC$ and $BC$ are diameters of $d_1$ and $d_2$, then $R\subseteq d_1\cup d_2$, as illustrated in the following picture (again with $h=1/2$):

enter image description here

The sum of the areas of these disks $d_1$ and $d_2$ is $2\pi(\frac{\sqrt{1+h^2}}2\,)^2=\pi(1+h^2)/2$, which is strictly less than the sum $\pi\,0^2+\pi\,1^2=\pi$ of the areas of the disks $D_1$ and $D_2$ optimally covering $R$ in terms of the sum of the perimeters.

Thus, the optimal covering of $R$ by two closed disks in terms of the sum of the perimeters is different from any optimal covering of $R$ by two closed disks in terms of the sum of the areas. $\quad\Box$

$\endgroup$
1
  • $\begingroup$ Your answer appears to have the consequence: for a given n and triangle T, to find the layout of disks with total min perimeter and covering T could be a quite a different problem from the one with min total area. And both could well be as difficult to settle as the layout of of n disks with max area that can be packed inside T. And this question remains: mathoverflow.net/questions/456324/… $\endgroup$ Commented Oct 16, 2023 at 17:27

You must log in to answer this question.

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