23
$\begingroup$

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).

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 11, 2014 at 7:15
  • $\begingroup$ @PeterDukes: For the version restricted to translations - perhaps so. $\endgroup$ Mar 11, 2014 at 16:18
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 11, 2014 at 19:56
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 11, 2014 at 20:28
  • 1
    $\begingroup$ @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! $\endgroup$ Mar 12, 2014 at 0:40

2 Answers 2

4
$\begingroup$

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 Minkowski 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 Minkowski Sum stuff very well in Chapter 13: Robot Motion Planning.

$\endgroup$
2
  • $\begingroup$ This looks like a good approach to the "translations only" version. $\endgroup$ Mar 11, 2014 at 16:31
  • $\begingroup$ @user111 editing large numbers of old questions pushes newer questions off the front page. Please stop. $\endgroup$ Dec 22, 2020 at 22:26
3
$\begingroup$

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


  Immobilizing theorem


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. :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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