Minimum number of partial triangulations (Q2107503)

From MaRDI portal





scientific article
Language Label Description Also known as
English
Minimum number of partial triangulations
scientific article

    Statements

    Minimum number of partial triangulations (English)
    0 references
    0 references
    0 references
    0 references
    1 December 2022
    0 references
    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.
    0 references
    Catalan number
    0 references
    convex hull
    0 references
    triangulation
    0 references
    quasi-convex set of points
    0 references
    partial triangulation
    0 references

    Identifiers