2
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.