Re: Finding edges of a given polyhedra in 3D

If you want to test only one or small-o(logn) edges the following
approach may be efficient :

Suppose you have to test if ((x_i, y_i, z_i), (x_j, y_j, z_j) is a
convex
polyhedral edge. Then these two points must be lineraly separable
from rest (n-2) points. So there must exist a separating hyperplane
a*x+b*y+c*z+d = 0.

Thus it is indeed a polyhedral edge if we have a feasible solution of
either of the following 2 LP :

a*x_k+b*y_k+c*z_k+d <= 0 (k <> i, j)

a*x_i+b*y_i+c*z_i+d >= 0

a*x_j+b*y_j+c*z_j+d >= 0

or

a*x_k+b*y_k+c*z_k+d >= 0 (k <> i, j)

a*x_i+b*y_i+c*z_i+d <= 0

a*x_j+b*y_j+c*z_j+d <= 0

Since we have linear time algorithm for solving 3 variable LP [Meggido]
(in fact it works in any fixed dimension) we can perform the entire
computation in linear time.

But if you have to test all edges it is better to compute the convex
hull
and extract the convex hull edges from DCEL ( a data structure to
represent planar graphs) and report other edges as diagonal edges.

Thanks

--- Pinaki

==================================================================

macio wrote:
Hello,

I have a problem to solve.

How can I find the edges of a polyhedra in 3D having only coordinates
of its vertices?
All the pairs of the vertices constitute corresponding line segments.
Some of them are diagonals and some of them are edges. I have to
distinguish them based only on the vertices data.

I searched a little and found no solution. I intended only very heavy
algorithm in 2D which consist on finding which of the line segments
intercept with each other in the area of the polyhedra (based on this I
could decide which is diagonal which is edge). This doesn't work of
course in 3D.

regards

.