A BASIS ENUMERATION ALGORITHM FOR LINEAR-SYSTEMS WITH GEOMETRIC APPLICATIONS

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of all bases, or all feasible bases, of a linear system. The algorithm has the following properties: no additional storage is required beyond the input data; the output list produced is free of duplicates; the running time is output sensitive for non-degenerate inputs; the algorithm is easy to efficiently parallelize. It can be used for various geometric enumeration problems including finding all facets of the convex hull of a set of points and the enumeration of all vertices of a convex polyhedron or hyperplane arrangement, and can be extended to oriented matroids.