ICS Theory Group

ICS 269, Winter 1996: Theory Seminar

1 March 1996:
Generating Triangulations without Repetitions
Jason Cahill, ICS, UC Irvine

(Based on a paper by D. Avis and K. Fukuda, to appear in Discrete Applied Math as "Reverse Search for Enumeration")

The reverse search technique has been recently introduced by the authors for efficient enumeration of vertices of polyhedra and arrangements. In this paper, the authors develop the idea in a broader framework and show its applications to various problems in operations research, combinatorics, and geometry.

In my talk, I will be discussing the motivations and details of reverse search, followed by a discussion of how it can be applied to the problem of generating all possible triangulations to a set of n points in the plane.