Let $S\subseteq\mathbb{R}^d$ be a finite set and $P=conv(S)$ its convex hull so $P$ is a convex polytope. Let $p\in P$ be given. Note that if $F_1$ and $F_2$ are two faces of $P$ containing $p$, then $F_1\cap F_2$ is also a face of $P$ containing $p$. Thus, there exists a smallest face $F$ of $P$ containing $p$. Is there a polynomial time algorithm (in $n$ and $d$) that computes this face $F$? $F$ can be given as $conv(S_1)$ for some $S_1\subseteq S$.
I realized that if I can write $P=\{x\mid Ax\leq b\}$ then the rest follows. However, as I find out, computing this presentation of $P$ is called the Face Enumeration Problem and does not admit a polynomial time algorithm (unless I assume that $d$ is fixed).
If $s \in S$, then $s \in F$ iff there is no $y \in \mathbb R^d$ with $y \cdot p \ge y \cdot x$ for all $x \in S$ and $y \cdot p > y \cdot s$. You can decide this using a polynomial-time algorithm for linear programming.