Vertex enumeration problem

In mathematics, the vertex enumeration problem for a <a href="/facts/Polytope/a76nXrL0">polytope</a>, a polyhedral <a href="/facts/Cell_complex/rN7buLMo">cell complex</a>, a <a href="/facts/Hyperplane_arrangement/78c23rYy">hyperplane arrangement</a>, or some other object of <a href="/facts/Discrete_geometry/Ixnl3GBc">discrete geometry</a>, is the problem of determination of the object's <a href="/facts/Vertex_(geometry)/ID3cea9z">vertices</a> given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a <a href="/facts/Convex_polytope/2pRHcRgC">convex polytope</a> specified by a <a href="/facts/Set_of_linear_inequalities/YGHD3tW5">set of linear inequalities</a>:

A
        x
        ≤
        b
      
    
    {\displaystyle Ax\leq b}

where A is an m×n matrix, x is an n×1 column vector of variables, and b is an m×1 column vector of constants. The inverse (<a href="/facts/Duality_(mathematics)/8jGuyQIU">dual</a>) problem of finding the bounding inequalities given the vertices is called <a href="/facts/Facet_enumeration/2pRHcRgC">facet enumeration</a> (see <a href="/facts/Convex_hull_algorithms/Wr70A2AI">convex hull algorithms</a>).

Vertex enumeration problem open-in-new

Vertex enumeration problem