Reverse Search: Origins


Komei Fukuda and I discovered the idea for reverse search during conversations in Tokyo in October 1990. Were were working on the vertex enumeration problem for convex polyhedra. At the time I was visiting Masao Iri at the University of Tokyo and Masakazu Kojima at Tokyo Institute of Technology, supported by a JSPS/NSERC bilateral exchange. We quickly saw that reverse search could be used for a number of related geometric enumeration problems, wrote it up, and published it as a T.I.T Technical Report:

A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
Tokyo Institute of Technology, Dept. of Informations Science, Research Report B-237, November 1990, 14 pages. pdf

A short while later, I explained the idea to Iri. He was enthusiastic, and invited us to submit a short note on the subject to the new journal, Applied Mathematics Letters, which had a very fast turnaround. Accordingly, our first journal paper on reverse search, without proofs, appeared in early 1991:

A basis enumeration algorithm for linear systems with geometric applications
Applied Mathematics Letters, Vol.4, Issue 5, 1991, Pages 39-42.  pdf

We submitted an extended abstract to the 7th ACM Symposium on Computational Geometry and a conference version of the paper appeared in June 1991. It was invited for a special issue of Discrete and Computational Geometry based on the conference, and the full journal version appeared in 1992:

A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
Discrete and Computational Geometry, Vol. 8, pp. 295-313 (1992). pdf

Meanwhile we began developing a whole range of other applications, both geometric and combinatorial. The list kept growing, so this paper took a lot longer to finish. It appeared in 1996:

Reverse search for enumeration
Discrete Applied Math, Vol. 6, pp. 21-46 (1996). pdf.

The latter two papers have been widely cited.

As a summer project in 2008, John White prepared a database of papers that cite one or other of the above papers.
He divided these citations into applications and implementations of reverse search.
He also prepared a demo to go along with a tutorial that I had written some time ago.
I am extremely grateful for his excellent work, and will endeavour to keep the databases reasonably up to date.

All contributions, corrections and suggestions are most welcome.

David Avis
October 28, 2008