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
$\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$
  • $\begingroup$ Thanks Fina, I'm familiar with Polymake. Its a fantastic program but its method for solving this particular question is cumbersome since one has to index the vertices and check the edge set manually... $\endgroup$ – Isaac Zebulun Burke Oct 1 '14 at 0:22
  • 1
    $\begingroup$ EDIT:: Polymake can do this job perfectly after all!! All you need is a small bit of experience with perl code. See forum.polymake.org/viewtopic.php?f=9&t=416 for the exact details. $\endgroup$ – Isaac Zebulun Burke Oct 1 '14 at 16:53
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$

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.