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

Question

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$).

Answer 1

This is an over-kill, but you can use the software Polymake to compute all edges of a polytope, which is given as a convex hull of a finite set.

Answer 2

Edited to add: I guess this answer doesn't really address the OP's question, since it sounds like he wants to write this code from the ground up.

---

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.