Reverse Search: Origins


Komei Fukuda and I discovered the idea for reverse search during conversations in his office in Tokyo, at the Myogadani campus of Tsukuba University, in October 1990. Were were working on the vertex enumeration problem for convex polyhedra. I was currently visiting 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 Masao Iri at the University of Tokyo. 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 3, 2008