Skip to main content
added 1690 characters in body
Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

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.

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.

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

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.

added 32 characters in body
Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

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.

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

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 for the cone example.

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

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.

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

Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

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 for the cone example.

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