Enumerating triangulation paths

Recently, Aichholzer introduced the remarkable concept of the so-called triangulation path (of a triangulation with respect to a segment), which has the potential of providing efficient counting of triangulations of a point set, and efficient representations of all such triangulations. Experiments support such evidence, although - apart from the basic uniqueness properties - little has been proved so far. In this paper we provide an algorithm which enumerates all triangulation paths (of all triangulations of a given point set with respect to a given segment) in time O(tn(3) log n) and O(n) space, where n denotes the number of points and t is the number of triangulation paths. For the algorithm we introduce the notion of flips between such paths, and define a structure on all paths such that the reverse search approach can be applied. We also refute Aichholzer's conjecture that points in convex position maximize the number of such paths. There are configurations that allow Omega (2(2n-Theta (log n))) paths. (C) 2001 Elsevier Science B.V. All rights reserved.