Reaching towards the limits of exhaustive search
Komei Fukuda, School of Computer Science, McGill University

Exhaustive search or complete listing is to generate all objects satisfying a prescribed property. The listing of all non-isomorphic graphs of a fixed number of vertices is a well known example. Computationally efficient listing demands both mathematically sound ideas and clever computational techniques. In this talk, we travel through a few recent examples of exhaustive search that were not possible before, and present critical mathematical and computational ideas. In particular, the problem of constructing an arrangement of hyperplanes and that of listing all combinatorial types of point configurations in the $d$-dimenstional real space will be discussed. We will see how the combinatorial abstraction of hyperplane arrangements and point configurations by oriented matroids becomes useful in solving the latter listing problem.


Announcement Poster in PDF