Computational Complexity
The computational complexity of the problem is a subject of research in computer science.
A 1992 article by David Avis and Komei Fukuda presents an 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. The Avis–Fukuda algorithm adapted the criss-cross algorithm for oriented matroids.
Read more about this topic: Vertex Enumeration Problem
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)