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 numbertriangulationconvex hullpartial triangulationquasi-convex set of points

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.

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

• 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?)
• 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).
• On the number of plane graphs
• The Number of Triangulations on Planar Point Sets
• Transforming triangulations
• Triangulations. Structures for algorithms and applications

Cited in

(6)

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

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)