I have a convex polyhedron (with integral nodes). I only calculate in euclidian spaces. Let N be the set of nodes, c the center (arithmetic mean) of the polyhedron.

I now want to determine if a line between two nodes is an edge of the polyhedron or is on a face of the polyhedron or not. In other words: i want to determine if there is a point on the line which isn't on the boundary of the polyhedron.

Let $ n,m \in N $ and $p^*=t^*\cdot n+(1-t^*)\cdot m$ the point with minimal distance to the center (i.e. $t^* = argmin_{t}(|p(t) - c|)$ ). I construct a plane through $p^*$ with normal vector $v=(c-p^*)$.

My intuition tells me that the line between $n$ and $m$ is an edge or a "diagonal" of a face of the polyhedron if and only if the plane does not split the polyhedron. In other words: if there exists no node $x \in N$ which satisfies $v\cdot (x-p^*)<0$, then the line is an edge of on a face.

Am I right about this? My mind isn't clear enough to see it right now. It's obvious in 2D, but my imaginations fails for higher dimensions (as I am dealing with at least six dimensions)

  • 1
    $\begingroup$ A side comment: you probably shouldn't call your normal vector the same name as one of your nodes. $\endgroup$ – Willie Wong Feb 26 '12 at 20:06
  • $\begingroup$ you're absolutely right, I'll fix that now $\endgroup$ – stefan Feb 26 '12 at 20:09
  • $\begingroup$ Also, by "edge" do you mean "boundary", or do you actually mean as in "vertex, edge, face" for polyhedra? For the latter definition what you want is clearly false: take a cube and two vertices that share a face but not an edge. $\endgroup$ – Willie Wong Feb 26 '12 at 20:10
  • $\begingroup$ uh, your right, but i want to allow that, will change the question. thanks $\endgroup$ – stefan Feb 26 '12 at 20:13
  • $\begingroup$ How are you defining the center of your polyhedron? There are several possibilities that come to mind here - or are you expecting your intuition to be the case for any point $c$ interior to the polyhedron? $\endgroup$ – Steven Stadnicki Feb 26 '12 at 20:14

It is not true if you are asking for "if and only if"

Take the regular dodecahedron centered at the origin. Pick one face, label the vertices around the pentagon in clockwise order $A,B,C,D,E$. Take $n = A$ and $m=C$. Then it is clear that

$$ v\cdot(B-p^*) < 0 $$


$$ v\cdot(E-p^*) > 0 $$

But if you are asking only for the one-way implication:

By convexity $p^*$ is in the (closed) polyhedron. If the equation is satisfied, it is easily checked that the plane you constructed through $p^*$ that is orthogonal to $v$ is a supporting plane of the polyhedron. Since the plane intersects at least two vertices of the polyhedron, it must contain at least an edge, and possibly a face, of the polyhedron.

  • $\begingroup$ i don't see why this example should be valid. I'm pretty sure my calculation is right and with n = A and m = b it yields for all vertices values of <= 0. Are you sure about your example? $\endgroup$ – stefan Feb 26 '12 at 20:56
  • $\begingroup$ of course i meant all values are >= 0, but thats just dependent on the definition of the normal vector. my statement is: alle the dot products have the same sign $\endgroup$ – stefan Feb 26 '12 at 21:08
  • $\begingroup$ sorry, typo. $m = C$ is what I intended. It is important to skip a node. The key is to make the plane containing $m,n,c$ and the face containing $m,n$ be transverse. $\endgroup$ – Willie Wong Feb 26 '12 at 23:08
  • $\begingroup$ you're right, thanks for your answer. do you have an idea about an criterion that holds "if and only if"? $\endgroup$ – stefan Feb 26 '12 at 23:39
  • $\begingroup$ One idea is to use the fact that projections of convex shapes are still convex, and assuming you have a workable criterion in 2D. That is: take the line $nm$, and take the orthogonal projection of $N$ to the plane that is perpendicular to $nm$. The entire segment $nm$ gets projected to a single point. If $nm$ is on the boundary, then this $k$ would be on the boundary. If $nm$ is in the interior, then $k$ would be in the interior. $\endgroup$ – Willie Wong Feb 27 '12 at 10:10

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.