# Trapping a convex body by a finite set of points

In $\mathbb{R}^n$, let $K$ be a convex body and $T$ a finite set of points disjoint from the interior of $K$. Say that $T$ traps $K$ if there is no continuous motion of $K$ carrying $K$ arbitrarily far away from its original position during which no point of $T$ penetrates the interior of $K$. Is there a finite number $k=k(n)$ such that each $n$-dimensional convex body $K$ can be trapped by a set of at most $k$ points? If so, what is the smallest such $k$? Observe that the $3$-cube can be trapped by six points, but not by five (for the $n$-cube it's $2n$ points, but not $2n-1$). The $n$-ball can be trapped by $n+1$ points, and it seems that no $n$-dimensional convex body can be trapped by $n$ points.

The main question is: Can every convex body in $\mathbb{R}^3$ be trapped by six points?

More generally: Can every convex body in $\mathbb{R}^n$ be trapped by $2n$ points?

Footnote 1. Here is a variation of the problem, perhaps easier to handle: restrict the motions of $K$ to parallel translations.

Footnote 2. For $n=2$, a closely related problem, namely of immobilizing the body with a finite set of points, has been studied and solved: four points always suffice. Reference will be provided upon request (I will have to look it up).

• In the translation case: I wonder if there is an argument which inducts on the dimension, say by using two points defining a "width" of $K$, followed by restriction to an orthogonal hyperplane. – Peter Dukes Mar 11 '14 at 7:15
• @PeterDukes: For the version restricted to translations - perhaps so. – Wlodek Kuperberg Mar 11 '14 at 16:18
• I just saw Yuliy Baryshnikov give a talk on related topics at the IMA (what he called "caging"). You might want to ask him for references. – Greg Friedman Mar 11 '14 at 19:56
• @PeterDukes: For $K$ smooth, there are normals in all directions, and you can pick $n+1$ points on the surface whose unit normal vectors have the origin in the interior of their convex hull. Any small translation will move one of these points into the interior. – Douglas Zare Mar 11 '14 at 20:28
• @DouglasZare: Yes, absolutely. I am not sure if inducting on the dimension works always, but it certainly isn't best possible in the smooth case. In general, I had the impression that one can usually do much better than $2n$. PS: Hi! It's nice to see you again after all these years, even if just on MO! – Peter Dukes Mar 12 '14 at 0:40

This is not an answer, just a reference on immobilizing in $\mathbb{R}^3$:

Bracho, J., Fetter, H., Mayer, D., & Montejano, L. (1995). Immobilization of solids and mondriga quadratic forms. Journal of the London Mathematical Society, 51(1), 189-200. (ResearchGate link)

They cite one W. Kuperberg from a 1990 presentation. :-)

I will assume we are not allowing re-orientation of the body (rotation).

If one wishes to determine if some arbitrary rigid body $K$ can pass some obstacle $T$ without touching it, one can reduce the problem to determining if some point $k \in K$ can pass by the minkowsky sum of $K$ and $T$ (which I will denote $K+T$) without touching it. In this case, if we wish to determine if $K$ can escape to infinity, assuming $K$ is bounded and finite, we need only determine if $K+T$ disconnects $\mathbb{R}^n$ into at least two connected components.

Since $T$ is a set of points, $K + T$ is simply taking $|T|$ copies of $K$, where each copy is centered at a point in $T$ (you can pick any point in $K$ to be the "center" of $K$, WLOG). Our question then becomes: what is the shape that maximizes the number of copies we would need to union together (without rotations) to disconnect $\mathbb{R}^n$ into two non-empty sets, and how many copies would that be?

I am fairly certain that proving that the $n$-cube is this shape, and that it requires $2n$ copies is a hop and a skip away from this, but I'm at a loss for a sufficiently formal argument. Something about how the faces are orthogonal and can only restrict one direction in one dimension at a time or something, which is somehow the worst-case. There's probably a similar argument for n+1 being a lower bound and tetrahedra. Unfortunately, this is where my knowledge stops.

de Berg et al's Computational Geometry: Algorithms and Applications covers the Minkowsky Sum stuff very well in Chapter 13: Robot Motion Planning.

• This looks like a good approach to the "translations only" version. – Wlodek Kuperberg Mar 11 '14 at 16:31