Determination of Edges of a Convex Polytope

Abstract

In this paper, the problem of determination of the edges of a convex polytope is considered. It is shown that this problem is equivalent to the standard linear programming problem and therefore can be solved by the simplex method. Further, for a special type of polytopes which are an affine transformation of a box we show that extremal points determine edges.

Bu çalışmada, konveks bir politopun kenarlarının belirlenmesi problemi ele alınmıştır. Bu problemin, simpleks yöntemiyle çözülebilen bir standart lineer programlama problemine denk olduğu gösterilmiştir. Ayrıca, bir kutunun afin dönüşüm altındaki görüntüsü olan özel politoplar için uç noktaların, politopun kenarlarını belirlediği gösterilmiştir.