Minimum number of partial triangulations

DOI10.1016/J.EJC.2022.103636MaRDI QIDQ2107503zbMATH OpenOpenAlexFDO

Authors Andrey B. Kupavskii, Aleksei Volostnov, Yury Yarovikov

Publication date 1 December 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.05855

zbMATH Keywords

Catalan numberconvex hullpartial triangulationquasi-convex set of pointstriangulation

Mathematics Subject Classification ID

Approximation by convex sets (52A27)

Abstract: We show that the number of partial triangulations of a set of $n$ points on the plane is at least the $(n-2)$-nd Catalan number. This is tight for convex $n$-gons. We also describe all the equality cases.

Review text

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.

Recommendations

• A lower bound on the number of triangulations of planar point sets
• An improved lower bound on the minimum number of triangulations
• Counting triangulations of balanced subdivisions of convex polygons
• Counting triangulations of some classes of subdivided convex polygons
• The Number of Triangulations on Planar Point Sets

Cites work

• A better upper bound on the number of triangulations of a planar point set
• A lower bound on the number of triangulations of planar point sets
• Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
• Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).
• scientific article; zbMATH DE number 5506218 (Why is no real title available?)
• scientific article; zbMATH DE number 5177 (Why is no real title available?)
• scientific article; zbMATH DE number 1409186 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• On the number of plane graphs
• The Number of Triangulations on Planar Point Sets
• Transforming triangulations
• Triangulations. Structures for algorithms and applications

Cited in

(7)

• On a property of minimal triangulations
• Minimum Wiener index of triangulations and quadrangulations
• Minimum balanced bipartitions of planar triangulations
• An improved lower bound on the minimum number of triangulations
• scientific article; zbMATH DE number 495506 (Why is no real title available?)
• Counting triangulations of balanced subdivisions of convex polygons
• Associahedra minimize f-vectors of secondary polytopes of planar point sets

This page was built for publication: Minimum number of partial triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107503)