Counting polygon triangulations is hard

DOI10.1007/S00454-020-00251-7zbMATH Open1460.52022arXiv1903.04737OpenAlexW3096901045MaRDI QIDQ2223620FDOQ2223620

Authors: David Eppstein 

Publication date: 29 January 2021

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We prove that it is $$-complete to count the triangulations of a (non-simple) polygon.

Full work available at URL: https://arxiv.org/abs/1903.04737

Recommendations

• Hard Enumeration Problems in Geometry and Combinatorics
• Counting trees in a graph is \(\# \text{P}\)-complete
• scientific article; zbMATH DE number 4108152
• The Complexity of Planar Counting Problems
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs

zbMATH Keywords

counting complexitypolygon triangulationnon-crossing subsetspolygons with holes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Title not available (Why is that?)
• The complexity of computing the permanent
• Flipping edges in triangulations
• On counting homomorphisms to directed acyclic graphs
• On the computational complexity of the Jones and Tutte polynomials
• Analytic combinatorics of non-crossing configurations
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• 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
• On the number of plane geometric graphs
• On the number of pseudo-triangulations of certain point sets
• Bounds on the maximum multiplicity of some common geometric graphs
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Counting triangulations of planar point sets
• How to draw a planar graph on a grid
• Title not available (Why is that?)
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• The complexity of counting in sparse, regular, and planar graphs
• Computational complexity of counting problems on 3-regular planar graphs
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Hard Enumeration Problems in Geometry and Combinatorics
• Triangulating planar graphs while minimizing the maximum degree
• Forbidden configurations in discrete geometry
• An improved lower bound on the minimum number of triangulations
• Note on the number of triangulations of planar point sets
• Counting and enumerating crossing-free geometric graphs
• An upper bound for the number of planar lattice triangulations
• Stochastic minimum spanning trees and related problems
• Point sets with many non-crossing perfect matchings
• An efficient algorithm for enumeration of triangulations
• Generating triangulations at random
• Computing and Combinatorics
• A QPTAS for the base of the number of crossing-free structures on a planar point set
• Counting triangulations and other crossing-free structures approximately
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• A simple aggregative algorithm for counting triangulations of planar point sets and related problems
• Counting triangulations and other crossing-free structures via onion layers

Cited In (5)

• Hard Enumeration Problems in Geometry and Combinatorics
• Perfect matchings with crossings
• Perfect matchings with crossings
• Computational complexity of counting coincidences
• Non-crossing Hamiltonian paths and cycles in output-polynomial time

This page was built for publication: Counting polygon triangulations is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223620)