On numbers of pseudo-triangulations (Q1947983): Difference between revisions

After having culminated the work of bounding the maximum number of plane graphs on a set of \(N\) points [\textit{M. Sharir} and \textit{A. Sheffer}, Lect. Notes Comput. Sci. 7704, 19--30 (2013; Zbl 1378.68185)] and, in particular, the lower and upper bounds of possible triangulations, the authors study similar problems related with pseudo-triangulations and pointed pseudo-triangulations. Some discrepancies with results existing in previous literature are carefully worked out. Among the main results, the authors show that the statement saying that the number of pointed pseudo-triangulations that can be embedded over a set \(S\) of \(N\) points is always lesser or equal than \(3^N\) times the number of distinct triangulation over \(S\) is not asymptotically tight. The bound can be improved a little bit. Instead of \(3^N\), the new bound is \(2.97^N\). It seems a very small improvement, but it is the first new result after a decade and it has potential to induce further progress.