A fast algorithm is proposed for checking the stability of the edges of a polytope where most of the computations involved depend on the number of vertices rather than on the number of edges. This algorithm is based on the segment lemma derived by H. Chapellat et al. (1988). Although the segment lemma is an important result on its own, no explicit algorithm was given there. Some important properties of the lemma are revealed, and it is shown how they lead to a fast algorithm. In this algorithm, the major computations involved are those of solving for the positive real roots of two polynomials with degree less than or equal to n/2 for each vertex. The computations required by the algorithm are mainly vertex-dependent, and the burden of the combinatoric explosion of the number of edges is greatly reduced.
展开▼
