Go backward to 3 Combinatorial Structure
Go up to Main Page
Go forward to 5 Optimization
|
Go backward to 3 Combinatorial Structure Go up to Main Page Go forward to 5 Optimization |
XHTML 1.0 |
Two polytopes P1 ⊂ Rd1 and P2 ⊂ Rd2 are affinely equivalent if there is a one-to-one affine map T : aff (P1) → aff (P2) between the affine hulls of P1 and P2 with T(P1) = P2. Two polytopes are combinatorially equivalent (or isomorphic) if their face lattices are isomorphic. It is not hard to see that affine equivalence implies combinatorial equivalence.
As soon as one starts to investigate structural properties of polytopes by means of computer programs, algorithms for deciding whether two polytopes are isomorphic become relevant.
Some problems in this section are known to be hard in the sense that the graph isomorphism problem can polynomially be reduced to them. Although this problem is not known (and even not expected) to be NP -complete, all attempts to find a polynomial time algorithm for it have failed so far. Actually, the same holds for a lot of problems that can be polynomially reduced to the graph isomorphism problem (see, e.g., Babai [3]).
|
|
Why are some symbols not displayed correctly? |