Minimum number of partial triangulations (Q2107503)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Minimum number of partial triangulations |
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
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