2010/12/10 by Roland Bacher, Bacher, Roland, Frédéric Mouton +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Point processes and geometric inequalities #math.CO
paper · pdf · doi:10.48550/arxiv.1012.2206
arxiv created 2010/12/10 · openalex publication_date 2010/12/10 · arxiv updated 2010/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Counting Euclidean triangulations with vertices in a finite set \C of the convex hull \conv(\C) of \C is difficult in general, both algorithmically and theoretically. The aim of this paper is to describe nearly convex polygons, a class of configurations for which this problem can be solved to some extent. Loosely speaking, a nearly convex polygon is an infinitesimal perturbation of a weakly convex polygon (a convex polygon with edges subdivided by additional points). Our main result shows that the triangulation polynomial, enumerating all triangulations of a nearly convex polygon, is defined in a straightforward way in terms of polynomials associated to the ``perturbed'' edges.