Longest line segment in a convex polyhedron in $\mathbb{R}^3$ in direction $\mathbf{n}$

Question

Let us consider a non-empty convex polyhedron $\mathcal{C} \subset \mathbb{R}^3$ and a vector $\mathbf{n} \in \mathbb{R}^3$. If we choose a point $\mathbf{x} \in \mathbb{R}^3$, then $ \mathbf{x}$ and $ \mathbf{n} $ define a line in $\mathbb{R}^3$. Let us denote the line by $\mathbf{p}_{\mathbf{x}}$.

I would like to pick such a point $\mathbf{x}$ in $\mathbb{R}^3$ that the interception of $\mathcal{C}$ and line $\mathbf{p}_{\mathbf{x}}$ is maximal. Let us denote the endpoints of a line segment given by the intersection of $\mathcal{C}$ and $\mathbf{p}_{\mathbf{x}}$ by $\mathbf{a}_{\mathbf{x}}$ and $\mathbf{b}_{\mathbf{x}}$. Hence, I want to solve the following optimization problem

$$ \underset{\mathbf{x} \in \mathbb{R}^3}{\text{argmax}} \| \mathbf{b}_{\mathbf{x}} - \mathbf{a}_{\mathbf{x}} \| .$$

I think that it would be impractical to formulate a general optimization problem and try to solve it numerically. I assume that we can use the convexity of $\mathcal{C}$ and only consider the lines that that follow direction $\mathbf{n}$ and pass through the vertices of $\mathcal{C}$. However, I don't know how to properly argument this and I would appreciate any advice.

Answer 1

Hint: If $\mathcal C$ has non empty interior it is enough to look for $\mathbf x$ inside $\mathcal C$ which is equivalent to solving the following linear program:

$$\max\, t :\, \mathbf y - \mathbf x = t\mathbf n,\, \mathbf x\in \mathcal C,\, \mathbf y\in \mathcal C$$

Answer 2

You say

I assume that we can use the convexity of $\mathcal{C}$ and only consider the lines that that follow direction $\mathbf{n}$ and pass through the vertices of $\mathcal{C}$.

Unfortunately, this isn't true. Consider the gyrobifastigium:

Suppose $\mathcal{C}$ is a shape roughly like this, with coordinates of $(\pm 1, \pm 1, 0)$, $(0,\pm 1, 1)$, and $(\pm 1, 0, -1)$. Take $\mathbf{n}$ to be the vector $(0,0,1)$, so we're trying to find the point above which $\mathcal{C}$ is "tallest".

Clearly, the maximum possible height is $2$, since $\mathcal{C}$ is bounded below by $z=-1$ and above by $z=1$. But this height is only attained at the segment from $(0,0,-1)$ to $(0,0,1)$, along which $\mathcal{C}$ has no vertices.

I believe we can assume that $\mathbf{x}$'s location on a plane $\mathbf{n}^\perp$ orthogonal to $\mathbf{n}$ is either a vertex of $C$ or the intersection of the projections of two edges of $C$ onto $\mathbf{n}^\perp$, so we can still restrict our attention to a finite set, but it might be substantially larger. (There are likely ways to prune this set to a more manageable size, though.)