Convexity Minimizes Pseudo-Triangulations

O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann

Abstract:

For standard triangulations it is not known which sets of points have the fewest or the most triangulations. In contrast, we show that sets of points in convex position minimize the number of minimum pseudo-triangulations. This adds to the common belief that minimum pseudo-triangulations are more tractable in many respects.

Reference: O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann. Convexity minimizes pseudo-triangulations. In Proc. $14th$ Annual Canadian Conference on Computational Geometry CCCG 2002, pages 158-161, Lethbridge, Alberta, Canada, 2002.