Covering a Triangle with Disks Centered on its Boundary
Let $\cal P$ be a triangle and $\cal D_{1}, \cal D_{2}$ be disks centered on the boundary of $\cal P$ with radii $r_{1}$, $r}{2}$. The disks are chosen so that $\cal D{1}$ $\cup$ $\cal D$${2}$ covers $\cal P$ and $r{1}$ + $r_{2}$ is minimized. We show that an optimal covering must exist with $r_{2}$ = 0. In such a single disk covering, $\cal D_{1}$ is always located on the longest side of $\cal P$. The exact location and and size depend on the angles of $\cal P$; we provide a complete characterization and then generalize it to convex polygons. We show that the minimum covering disk can be determined in $\cal O (n)$ time for a convex polygon with $n$ sides. However, it is open for $n \geq$ 4 whether there is always a single disk covering that is optimal.