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.

  • 2
    $\begingroup$ 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. $\endgroup$ – user25199 Jun 2 '15 at 13:38
  • 3
    $\begingroup$ 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. $\endgroup$ – Dylan Thurston Jun 2 '15 at 14:16
  • 1
    $\begingroup$ @DylanThurston: Good point. So perhaps only if $P$ lies in a hemisphere does the hull make sense. $\endgroup$ – Joseph O'Rourke Jun 2 '15 at 15:12

This is the germ of an answer to suggest that a connected but not simply connected region R can be built that may have arbitrarily large area, and in any case an area larger than that occupied by the convex hull.

R is going to be the union of great circles, so if P lies on a great circle, then this won't work. In particular, R will be patterned after a beach ball, so it will be the union of circular wedges. Which wedges? That's the tricky part.

One can start by "measuring" the set P: see how small a wedge contains P from all directions, and see how large a wedge contains all but one point of P when used in all directions. Further, for some arrangements of wedges, it is useful to know how far the "missing" point is from an existing wedge.

When one has these measurements, one now tries to add more and more wedges to R while avoiding any rotation that covers the point set P. Even if one uses only one wedge, it should be clear that for many "narrow" point sets P, a region R which avoids P can have an area more than twice that of the area of a small convex hull containing P.

Gerhard "Wasn't At A Beach Today" Paseman, 2015.06.07

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.