Worst-Case Addition to Smallest Enclosing Circle

126 Views Asked by At

Imagine you have a convex polygon $p_1$ and put a smallest enclosing circle $SEC_1$ around it, the lengths of each side of the polygon $l_i$ can be anything and don't have to equal each other. Now, imagine on each side of the polygon, you place a (45-45-90) triangle where the $l_i$ is the base of each triangle and $l_i$ is across from (opposite) the 90 degree angle. The triangles and $p_1$ combine to form $p_2$, which is then surrounded by a smallest enclosing circle $SEC_2$. The question is: what is the shape of $p_1$ that would cause the largest increase (in diameter or area) of $SEC_1$ to $SEC_2$?

1

There are 1 best solutions below

0
On

I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $\sqrt 2$ so the area doubles.

Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.

$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=\frac 12|DE|$. We note that $|AF|=x+\sqrt{1-x^2}$. This is maximized when $x=\frac 12\sqrt 2, |AF|=\sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.

enter image description here