Generating All the Faces of a Polyhedron

Abstract

The determination of all the extreme points of a given convex polyhedron P subset (R sup n) generally requires a substantial amount of computations; the note presents a conceptually simple algorithm for this purpose. Unlike other methods, the procedure generates only those basic solutions which are extreme points (i.e., only feasible basic solutions). More generally, this approach is able to generate all the faces of any dimension k (0 < or = k < or = n), that is all those k-dimensional subpolynedra which lie on the boundary of the given polyhedron P.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1971
Accession Number
AD0740333

Entities

People

  • Claude-alain Burdet

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computations
  • Computer Programming
  • Computing-Related Activities
  • Construction
  • Convex Programming
  • Decomposition
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Military Research
  • Optimization
  • Quadratic Programming
  • Two Dimensional

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design