Minimum number of partial triangulations (Q2107503)

Consider a set of points on the plane, denoted by \(M\), and denote by \(M_{c}\) the set of all vertices its convex hull, \(\mathrm{conv}(M)\). A triangulation of \(\mathrm{conv}(M)\) such that the set of vertices of the triangulation is \(M\) is called a full triangulation of \(M\). A triangulation of \(\mathrm{conv}(M)\) such that the set of its vertices \(V\) satisfies the condition \(M_{c} \subset V \subset M\) is called a partial triangulation of \(M\). The authors prove the following conjecture, raised by Emo Welzl during the Oberwolfach meeting on Discrete geometry in September 2020: ``Convex \(n\)-gons minimize the number of partial triangulations among any point sets in general position''. As a consequence, it means that any set of \(n\) points on the plane in general position has at least \(W_{n}=c_{n-2}\) (with \(W_2 = 1\)) partial triangulations, \(c_{n-2}\) being the \((n-2)\)-th Catalan number. A set of points \(M\) is said to be quasi-convex if each interior point of \(M\) is close to some side of \(\mathrm{conv}(M)\). The authors prove that any set of \(n\) points on the plane, in general position, has at least \(W_n\) partial triangulations. A set of \(n\) points has exactly \(W_n\) triangulations if and only if it is quasi-convex.