| Article ID: | iaor1997941 |
| Country: | Netherlands |
| Volume: | 70 |
| Issue: | 1 |
| Start Page Number: | 27 |
| End Page Number: | 45 |
| Publication Date: | Oct 1995 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Murty Katta G., Chung Sung-Jin |
| Keywords: | polytopes |
The authors introduce the concept of a segment of a degenerate convex polytope specified by a system of linear constraints, and explain its importance in developing algorithms for enumerating the faces. Using segments, they describe an algorithm that enumerates all the faces, in time polynomial in their number. The role of segments in the unsolved problem of enumerating the extreme points of a convex polytope specified by a degenerate system of linear constraints, in time polynomial in the number of extreme points, is discussed.