Equality of 2 descriptions

[Mathieu Dutour]

Hi

Suppose we have a set of rays (R) and a set of hyperplane half spaces
(H) [ie sets defined by sum_{1<=k<=n} a_ik x_k >=0]
We assume that these two sets are non redundant (my last question), ie
no ray is a positive sum of its other and no inequality is implied
by the other inequality.
What interest me is characterizing the equivalence of the two possible
description
--by extreme rays
--by facets
One more condition that appear is a rank condition, ie for any element
H1 of (H) the rank of the rays incident to H1 is n-1. By duality the
rank of the Hyperplanes incident to a ray R1 must also be n-1.

This condition does not suffice to tell that the two
description are equivalent.[think of the dodecaedron with one vertex
removed]

There exist numerous program that compute the extreme rays from the
facets and facets from the extreme rays.
Fukuda in his FAQ tell that it is unknown whether this problem is in P
or coNP complete.
My question is: does there exist program testing the equivalence of
the two descriptions without computing the dual description.

Mathieu

[Lutz Tautenhahn]

"Mathieu Dutour" <dut...@nef.ens.fr> schrieb im Newsbeitrag
news:9j22d7$187q$1...@nef.ens.fr...

Hello again Mathieu,

every extreme ray is the intersection of exactly d-1
of the non redundant hyperplanes (d=dimension).
Every hyperplane is restricted by exactly d-1 of
the non redundant extreme rays.
These conditions are necessary, but (as you mentioned)
not sufficient. So we need one more condition:
The scalar product of a normal vector of any hyperplane
(which points to the feasible region)
with any of the extreme rays must be >=0.
I think this will do it.

equivalent=true;
for j = 1 to number_of_extreme_rays begin
n:=0:
for i = 1 to number_of_hyperplanes begin
s:= ScPr(h[i],r[j]);
if s < -epsilon then equivalent=false;
if s < epsilon then n := n+1;
end;
if n<>d-1 then equivalent=false;
end;
for i = 1 to number_of_hyperplanes begin
n:=0:
for j = 1 to number_of_extreme_rays begin
if ScPr(h[i],r[j]) < epsilon then n := n+1;
end;
if n<>d-1 then equivalent=false;
end;

h[i] is a normal vector of the hyperplane i, r[j] is the
vector of the extreme ray j and ScPr(h[i],r[j]) is the
scalar product of both vectors.
Before calculating I would do a normalization of the
vectors. Take care of the right choice for the epsilon.

Regards, Lutz.