# Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$.

I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$.

Given $u_1, u_2 \in F$, is the line segment $[u_1,u_2]$ an edge of $P$?

I'm looking for a program that will answer this efficiently i.e I want to be able to simply feed it with $(a)$ a file containing the vectors of $F$ e.g

0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1

0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1

0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0

0 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0

0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0

0 0 0 0 0 0 1 1 0 2 0 0 0 0 0 0

0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0

and $(b)$ two special vectors in $F$ e.g.

$u_1 =$ 0 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0

$u_2 =$ 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0

and I want it to return $YES$ if $[u_1,u_2]$ is an edge of $P$ and $NO$ otherwise. The file that I feed the program may or may not contain interior points (all points in $F$ may not be vertices of $P$).

First (perhaps this is assumed) you should check that $u_1$ and $u_2$ are vertices of $P$. (Eg, this can be done by checking that the convex hull of $F\setminus\{u_i\}$ is different from the convex hull of $F$.)
Now project $F$ into $\mathbb Q^{d-1}$ along the direction $u_1-u_2$. (Express the points of $F$ in terms of a $\mathbb Q$-basis, one basis vector of which is $u_1-u_2$, then forget that component.) The vertices $u_1$ and $u_2$ now define a single point $p$ in $\mathbb Q^{d-1}$. Consider the convex hull of the projections of the points in $F$. Now $p$ is a vertex of the contex hull iff $[u_1,u_2]$ was an edge of P.