Complete enumeration of small realizable oriented matroids (Q1943649)

This paper deals with algorithms to completely enumerate realizable oriented matroids of given rank and number of elements. This has important applications as it yields the enumeration of combinatorial types of point configurations and polytopes, both being prominent problems in computational geometry. The authors recombine existing methods and contribute a new one to attack the NP-hard problem of deciding oriented matroid realizability. The resulting methods are involved and concerned with size-reduction of polynomial systems and the search for their solutions. As an application and based on the enumeration of oriented matroids of small rank and number of elements, the realizable oriented matroids of rank \(3\) and \(6\) on \(9\) elements and of rank \(4\) on \(8\) elements are enumerated. These questions have been open for a while and several methods applied by several teams of researchers failed to completely enumerate. As a corollary to these results all combinatorial types (including degenerate one) of \(3\)-dimensional configurations of \(8\) points, \(2\)-dimensional configurations of \(9\) points, \(5\)-dimensional configurations of \(9\) points, and \(5\)-dimensional polytopes with \(9\) vertices are enumerated. The numbers of combinatorial types in all the above cases are huge, and realizations of all realizable oriented matroids and final polynomials of non-realizable ones in the computed range can be found on a web page given in the paper.