Convexity Minimizes Pseudo-Triangulations
O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann
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. Annual Canadian Conference on Computational Geometry CCCG
2002, pages 158-161, Lethbridge, Alberta, Canada, 2002.