Number of bitangents to convex polytopes

Question

Let me state my question prior to defining terms:

Q. Let $P_1$ and $P_2$ be disjoint convex polytopes in $\mathbb{R}^d$ of $n$ vertices each. What is the maximum number of distinct bitangent $(d{-}1)$-dimensional hyperplanes realizable, as a function of $n$ and $d$, the maximum over all such polytopes?

In $\mathbb{R}^2$, the hyperplanes are lines, and the polytopes are polygons.

Say a hyperplane $H$ is tangent to a polytope $P$ if (a) $H$ contains at least one vertex, and (b) the interior of $P$ lies to one side of $H$. $H$ is a bitangent to $P_1$ and $P_2$ if it is (a) tangent to both (and so contains at least one vertex of both), and (b) $H$ contains at least $d$ vertices total. Say that two bitangents are distinct if the vertices of the polytopes they include are not identical.

So in $\mathbb{R}^2$, a bitangent contains $\ge 2$ vertices, and the answer to Q is $4$ independent of $n$ (thanks to Gerhard Paseman for this):

---

         
          ^{Bitangents to squares.}

---

In $\mathbb{R}^3$, a bitangent plane includes $\ge 3$ vertices. One can arrange two polyhedral convex cones $P_1$ and $P_2$ so that for each of $n-1$ vertices of $P_1$, there are $n-1$ different bitangent planes through two vertices of $P_2$:

---

         
          ^{Bitangents to polyhedral cones. Two bitangents shown.}

---

So the answer to Q for $d=3$ is $\Omega(n^2)$. Correction. As Gerhard pointed out, many of these supposed bitangent planes cut the cones. So in fact this example only shows $\Omega(n)$ bitangent planes.

My question is: How many distinct bitangent hyperplanes can there be in dimension $d$, for $d \ge 3$?

Answer 1

Note that a plane containing $k \lt d$ points of a convex polytope must contain the face having those $k$ points. So a weak upper bound on your number is a product of two numbers, each of which counts the number of permissible faces of each polytope.

Let's suppose we have fixed d-1 points in general position of our prospective bitangent and are seeking another point to fix it in place. If the first d-1 are distributed among both polytopes, then the next candidate (a) has to be in general position with the first d-1 points, and (b) has to be adjacent as in belonging to a polytope face that contains some of the d-1 points. So this limits the possibilities significantly.

If one polytope has all d-1 points, then there is even less freedom. As in the two dimensional case, sweeping a plane around a fixed subspace of codimension 1 gives up to four distinct possibilities for bitangential contact with at least one of two convex bodies. So I challenge the lower bound assertion ($\Omega(n^2)$ at this writing) for the cone example.

Edit 2019.05.20:

Here is an idea which may lead to an $\Omega(n)$ upper bound. However, we have to redefine the problem to make the idea work.

As observed in a comment, there are situations which could involve infinitely many bitangents, for example two aligned cubes on top of one another get four families of bitangents at each of four corners. We remove this case by requesting that d of the vertices in the bitangent plane are in general position, so that only one plane goes through those d vertices.

Now onto the argument. Suppose we have a bitangent with d vertices. We pick one of the d vertices to free, and now wobble the plane. There is only one degree of freedom, so if it does wobble there are (by arguments we have seen before) only four possibilities at most for the plane to touch tangentially one of the two convex polytopes, and we just left one of them. I am going to suggest (not prove) that there is only one other.

If so, then we can repeat this wobble, going from one bitangent to the next finding a point to release and acquiring a new point. Since there are only 2n points in total, there are at most 2n distinct planes realized on this tour.

I believe that there are two tours realized this way, those which intersect a line segment joining an interior point from each body, and those that do not. Again, I assert without proof. In the 2d case, we may have to pass to a tangent plane to one of the bodies before encountering the next bitangent, and the same may hold true in higher dimensions. However, I believe the bitangents are limited to 4n in number, because one cannot take an arbitrary face from each body. End Edit 2010.05.20.

Gerhard "Let's Face Up To It" Paseman, 2019.05.15.

Answer 2

This is not an answer, but an appropriate (as for me) way of thinking about the problem.

$P_1$ and $P_2$ are considered as the sets of vectors (from some point $O$ to all their points). Let $V_i$ be the set of vertices of $P_i$. Consider the Minkowski sums $Q_+=\frac12(P_1+P_2)$ and $Q_-=P_1+(-P_2)$. Assume that $H$ is a common tangent to $P_1$ and $P_2$.

If $P_1$ and $P_2$ lie on different sides of $H$, then all vertices of $Q_-$ in $(V_1\cap H)+(-V_2\cap H)$ lie in a supporting hyperplane of $Q_-$ parallel to $H$ and passing through $O$. If $H$ contains $d$ vertices in a general position, then $H\cap Q_-$ is a facet of $Q_-$.

Conversely, any facet of $Q_-$ is a difference of two faces of $P_1$ and $P_2$ whose sum of dimensions is $d-1$. So tis half of the question boils down to finding an upper bound tor the number of facers of $Q_-$ whose hyperplanes contain $O$.

In a similar manner, each bitangent hyperplane containing $P_1$ and $P_2$ on one side is a supporting hyperplane of $Q_+$ containing its facet. But in this case I do not see a clear condition on that facet…

Anyway, even the first half may be helpful in constructing polytopes with a large number of bitangent hyperplanes…