The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a polyhedron which is given in terms of finitely many linear equations and inequalities.

One way to measure the complexity of an enumeration algorithm is the total time used to compute all solutions. An output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. The number of solutions may be exponential in the size of the input, therefore a problem is tractable and said to be output polynomial when it can be solved in polynomial time in the size of the input and output.

The precise complexity status of the convex hull problem is unsettled: it is not known whether or not there exists an algorithm whose complexity is bounded by a polynomial in the combined size of the input and the output[1].

Unlike the well known convex hull algorithms, there is "the ultimate convex hull algorithm" which is an optimal output-sensitive algorithm by Kirkpatrick and Seidel in 1986 and a simpler algorithm was developed by Chan in 1996 [2].

Are there any known related results about the complexity of the convex hull problem? Even it is not output-sensitive. What caused the difficulty of this problem?

[1] Assarf, Benjamin, et al. "Computing convex hulls and counting integer points with polymake." Mathematical Programming Computation (2016): 1-38.

[2] https://en.wikipedia.org/wiki/Convex_hull_algorithms


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy