# Regions on a sphere that avoid a fixed point set

Let $P$ be a finite set of points on a unit-radius sphere $S$ in $\mathbb{R}^3$. Treat $P$ as a fixed pattern that can be rigidly slid around $S$ as a unit (no reflection).

Let $R$ be a subset of $S$. Say that $P$ fits in $R$ if there is some placement of $P$ such that each point of $P$ is strictly in the interior of $R$. Finally, say that $R$ avoids $P$ if $P$ cannot fit in $R$.

For example, let $P$ be the $n{=}5$ points shown below; I've drawn in the convex hull (blue) and an enclosing circle (red) for perspective. A hemisphere does not avoid $P$, because $P$ easily fits in a hemisphere.

My question is:

Q. What is the largest-area region $R$ that avoids a given set $P$?

Here area is the measure of $R$.

The convex hull of $P$ avoids $P$ (above, the hull is the illustrated quadrilateral formed of (blue) geodesic arcs), because the vertices of the hull are not strictly interior to the hull. A larger region that avoids $P$ is the smallest enclosing disk, whose boundary is outlined in red above. But I believe this is not the largest $R$ that avoids this particular $P$, for a slightly larger disk with an annular hole to "capture" the interior $5$th point has larger area.

The problem feels different if (a) $P$ fits in a hemisphere, and (b) all points of $P$ lie on its convex hull.

It is likely this question has been considered before, in which case I'd appreciate a reference. The same question may be asked for spheres in $\mathbb{R}^d$ for arbitrary $d$.

Update (23Oct15). I posed this question at the Canadian Conference on Computational Geometry, and a participant, Alexandru Damian, proved that, for an $n$-point set $P$, the area of an avoiding set cannot be larger than $\frac{n-1}{n} A$, where $A$ is the area of the sphere. The argument is sketched here (PDF download). The bound is tight for $n=2$ antipodal points.

• Not sure about the general case, but something related to this came up towards the end of a recent paper "Connectivity of confined 3D networks with anisotropically radiating nodes." O. Georgiou, C. P. Dettmann and J. P. Coon, IEEE Trans. Wireless Commun. 13, 4534-4546 (2014). In order to ensure connectivity for randomly oriented transmitters in a cube domain, we needed the $P$ with the smallest number of points which avoids the sphere minus an octant. It seems the answer is $14$, arranged as a gyro-elongated hexagonal bipyramid. – user25199 Jun 2 '15 at 13:38
• It's not true in general that the convex hull of $P$ avoids $P$. If $P$ is four points at the vertices of a regular tetrahedron, then the convex hull of $P$ is the whole sphere, which obviously does not avoid $P$. This makes me suspicious about more general cases of $P$ and its convex hull. – Dylan Thurston Jun 2 '15 at 14:16
• @DylanThurston: Good point. So perhaps only if $P$ lies in a hemisphere does the hull make sense. – Joseph O'Rourke Jun 2 '15 at 15:12