Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials
Hong Duc Bui · 2025
Read Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials by Hong Duc Bui (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09615.txt.
Introduction
Hong Duc Bui revisited the counting of triangulations in 2025, the ways a set of points in the plane can be carved into triangles using the points as corners. Two earlier research groups had each invented a polynomial whose values count triangulations, Bacher and Mouton on one side, Rutschmann and Wettstein on the other. And the relationship between the two inventions was unclear. Bui builds a single method in which both polynomials find their place.
Inside that method, the triangulation polynomials before defined only for chains of points extend to a wider class of setups the author calls near-edges. This makes the number of triangulations of several point-set groups efficiently computable. Bui also tried to sharpen the best known result of Rutschmann and Wettstein using the unified view and failed. An honest negative result the paper reads as evidence their bound is close to optimal already.
Catalog record
| CREATOR | Hong Duc Bui |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-09615
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials Hong Duc Bui Abstract We describe a framework that unifies the two types of polynomials introduced in [ 5 , 19 ] to analyze the number of triangulations of point sets. Using this insight, we generalize the triangulation polynomials of chains to a wider class of near-edges, enabling efficient computation of the number of triangulations of certain families of point sets. We use the framework to try to improve the result in [ 19 ] without success, suggesting that their result is close to optimal. 1 Introduction We are concerned with the problem of counting the number of possible ways to triangulate a given point set. See fig. 1 for an illustration of a triangulation. Figure 1: Example of a triangulated point set. More formally, given a set of distinct points P on the plane with no three points collinear, an edge of P is a line segment connecting two points in P , and a triangulation of P is a maximal set of non-intersecting edges. Sometimes, we are also concerned with the problem of counting the number of possible ways to triangulate a given polygon instead. Here, instead of a point set we are given a non-self-intersecting polygon P=P_{1}P_{2}\dots P_{n} , and a triangulation is a maximal set of non-intersecting diagonals of P . We still assume no three points within the vertices of P are collinear. It can be shown that the triangulation consists of exactly n-3 diagonals, where n is the number of sides of P . See fig. 2 for an illustration, note that unlike the case of triangulating a point set, edges lying outside P is not considered. Figure 2: Example of a triangulated polygon. We ask the following question: Let f(n) be the maximum number of triangulations of a point set with n points. What is the rate of growth of f(n) ? We know that f(n)\in O(30^{n}) thanks to a series to successive improvement [ 24 , 11 , 21 , 20 , 23 , 22 ] . Thanks to another series of successive improvements on the opposite direction [ 17 , 3 , 12 , 19 ] , it is known that f(n)\in\Omega(9.08^{n}) . The method of proving a lower bound f(n)\in\Omega(c^{n}) is to provide an explicit family of point sets and prove that it has at least \Omega(c^{n}) triangulations. Usually, proving the number of triangulations is the hard part. Part of the reasons for the difficulty is that the known methods for counting number of triangulations of a point set takes exponential time [ 4 , 15 ] , but more importantly, there is usually not enough structure on the collection of triangulations to effectively compute the number of triangulations in closed-form. This is where the technique in [ 19 ] proves useful: it defines a family of point sets, called chains , where to each chain C a upper triangulation polynomial T_{C}(x) is associated. This polynomial can be computed in quadratic time with respect to the number of points on the chain; furthermore, the algorithm to compute the triangulation polynomials can be easily modified to compute the total number of triangulations. In this article, we define a generalization, joint triangulation polynomials a_{A}^{yu}(y,u) which is a bivariate polynomial, and defined for all point sets A that is a near-edge . This article is organized as follows. In section 2 , an exposition of existing ideas is explained in order to motivate the definition of the maps \mathcal{T} and \mathcal{M} . In section 3 , we formally define a near-edge and related concepts. In section 4 , we formally define the joint triangulation polynomials associated to each near-edge, which is to be used in section 5 to count the number of triangulations of a near-edge, as well as a point set with near-edges glued to its sides. In section 6 , we further develop the algebraic theory, which is used in section 7 to simplify the statement of a certain theorem in [ 19 ] . In section 8 , we conjecture a similar statement for near-edge, and describe experiments conducted to attempt to improve the bound \Omega(9.08^{n}) described above. The data obtained from running the experiments are included in appendix A . 2 Motivation 2.1 Count Triangulations by Inclusion-Exclusion: Example We start with an exposition of [ 13 , Proposition 1] . For an arbitrary polygon P , let T(P) be the number of triangulations of P . We may also draw the polygon itself in the place of the polygon, for example T(\triangle)=1 (the polygon is literally a triangle). We also have for example T(\square)=2 , T(\hbox to6.97pt{\vbox to6.65pt{\pgfpicture\makeatletter\hbox{\hskip 3.48363pt\lower-3.00067pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {}{{}}{} {}{} {}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.5pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 4.47 1.45 L 0 4.7 L -4.47 1.45 L -2.77 -3.81 L 2.77 -3.81 Z}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}})=5 , T(\hbox to6.39pt{\vbox to7.3pt{\pgfpicture\makeatletter\hbox{\hskip 3.19449pt\lower-3.65001pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {}{{}}{} {}{} {}{} {}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.5pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 4.07 2.35 L 0 4.7 L -4.07 2.35 L -4.07 -2.35 L 0 -4.7 L 4.07 -2.35 Z}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}})=14 , this is just the Catalan numbers. Formally, define the n -th Catalan number to be C_{n}=\frac{1}{2n+1}\binom{2n+1}{n} , then when P is a convex polygon with n edges, T(P)=C_{n-2} . Proposition 1 . Notice that the only difference between the 3 polygons depicted in the equation is within the edges colored red. Figure 3: Illustration for the inclusion-exclusion principle. Let us explain more formally what we mean. We say a point set is in general position when no three points in the set are collinear. Let P=P_{1}P_{2}\dots P_{n} be an arbitrary polygon with vertices in general position, depicted in fig. 3 . The edge P_{1}P_{2} is marked in red. Let A be a point very near edge P_{1}P_{2} inside the polygon, but not very near either vertex. Let B be a point very near A , but outside the polygon. Define polygons P_{A}=P_{1}AP_{2}P_{3}\dots P_{n} and P_{B}=P_{1}BP_{2}P_{3}\dots P_{n} . We get three slightly-different polygons: P , P_{A} , and P_{B} . Then the proposition claims T(P_{A})+T(P)=T(P_{B}). Proof 2.1 . Each triangulation of P_{B} either contains the edge P_{1}P_{2} , or it doesn’t. There is a bijection between the triangulations of P_{B} that does contain edge P_{1}P_{2} and the triangulations of P , and there is a bijection between the triangulations of P_{B} that does not contain edge P_{1}P_{2} and the triangulations of P_{A} . Remark 2.2 . It matters where A and B is along the edge P_{1}P_{2} . In the situation depicted in fig. 4 , point A is outside angle \angle FGH but point B is inside, which leads to complication because triangle GHB does not intersect triangle GHC , but triangle GHA does. Figure 4 : Example where the location of A and B along the edge P_{1}P_{2} matters, as pointed out in remark 2.2 . 2.2 Generalization of Inclusion-Exclusion: Count Triangulations of the Double Circle The double circle point set is a point set with 2n vertices, where n of them forms a regular convex polygon with n vertices, and the remaining n