Suppose $n$ points in $\mathbb{R}^d$ form the vertices of a convex, bounded polytope $P$ with positive volume. I have two questions:
- is there a largest star polytope ($S$, say) with kernel equal to $P$?
- If so, are there algorithms for constructing the vertices of $S$?
I actually have a conjecture: the answer is yes for Q1, and regarding Q2, $S$ can be obtained as follows. $P$ satisfies $P=\{x\in \mathbb{R}^d: Ax\le b\}$ for some $k\times d$ matrix $A$ and some $b\in\mathbb{R}^d$. ``$\le$'' should be understood component-wise here. Then, letting $A_{-j}$ denote the submatrix of $A$ with row $j$ removed (and similarly for $b_{-j}$), $S$ satisfies $$S=\cup_{j=1}^k \{x: A_{-j} x\leq b_{-j}\}.$$ Is that right?
Edit: some simulations suggest that the conjecture could be correct for $d=2$. However, the corresponding algorithm I have used is quite inefficient because it requires (i) a facet enumeration to obtain $A$ and $b$; (ii) $k$ vertex enumerations to obtain the vertices of $\{x: A_{-j} x\leq b_{-j}\}$ for $j=1…k$. Also, this construction does not seem to work for $d>2$.