A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:[1] 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 (dual) problem of finding the bounding inequalities given the vertices is called facet enumeration (see convex hull algorithms).
For unbounded polyhedra, the problem is known to be NP-hard, more precisely, there is no algorithm that runs in polynomial time in the combined input-output size, unless P=NP.
[2] A 1992 article by David Avis and Komei Fukuda[3] presents a reverse-search algorithm which finds the v vertices of a polytope defined by a nondegenerate system of n inequalities in d dimensions (or, dually, the v facets of the convex hull of n points in d dimensions, where each facet contains exactly d given points) in time O(ndv) and space O(nd).
The v vertices in a simple arrangement of n hyperplanes in d dimensions can be found in O(n2dv) time and O(nd) space complexity.