How good are convex hull algorithms?
David Avis, David Bremner · 1995
A convex polytope is the bounded intersection of finite set H of halfspaces. A classic theorem of convexity theory is that every convex polyhedron can be expressed as the convex hull of its set V of vertices. There are three closely related computational problems related to the two descriptions of a polytope. The vertex enumeration problem is to compute V from H. The convex hull problem it to compute H from V. The polytope verification problem is to decide whether a given vertex description and halfspace description define the same polytope. The first two problems are essentially equivalent under point/hyperplane duality. It is an open problem whether any of these problems can be solved in time polynomial in jHj + jVj. In this paper we describe hard polytopes for convex hull algorithms based on pivoting , those based on triangulation, and for some insertion algorithms. 1 Introduction Although the simplex method had long been regarded as a practical and efficient algorithm for linear...