Counting Polygon Triangulations is Hard

2019/01/01 by David Eppstein · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Computational Geometry and Mesh Generation #Mathematics and Applications #Advanced Mathematical Theories and Applications #Polygon (computer graphics) #Combinatorics #Simple (philosophy) #Rectilinear polygon #Simple polygon #Polygon covering #Computer science #Mathematics #Monotone polygon #Geometry

paper · pdf · doi:10.4230/lipics.socg.2019.33

openalex publication_date 2019/01/01 · openalex created_date 2019/04/01 · openalex updated_date 2026/08/05

Abstract

We prove that it is #P-complete to count the triangulations of a (non-simple) polygon.

Cited by

• Polygon triangulation [wikipedia]

Related

• Counting Triangulations of Fixed Cardinal Degrees
• Counting Triangulations of Planar Point Sets
• Counting Triangulations of Configurations
• Enumerating triangulations by parallel diagonals
• A better upper bound on the number of triangulations of a planar point set