2
$\begingroup$

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)

  • 0
    thanks for your comments, by center i mean the arithmetic mean of all nodes. updated the question2012-02-26

1 Answers 1

1

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 $

while

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

  • 0
    since the orthogonal projection of$N$to the plane perdendicular to `nm` is still of dimension n-1 this does not seem to be an efficient way of checking this property in e.g. dimension 18 or higher. But thank you for your attempt :)2012-02-29