Counting Polygon Triangulations is Hard
- PDF / 684,525 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 210 Views
Counting Polygon Triangulations is Hard David Eppstein1 Received: 13 September 2019 / Revised: 31 July 2020 / Accepted: 21 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We prove that it is #P-complete to count the triangulations of a (non-simple) polygon. Keywords Polygon triangulation · Polygons with holes · Counting complexity · Non-crossing subsets Mathematics Subject Classification 52C45 · 68U05 · 68Q17
1 Introduction In 1979, Leslie Valiant published his proof that it is #P-complete to compute the permanent of a 0–1 matrix, or equivalently to count the perfect matchings of a bipartite graph [44].1 This result was significant in two ways: It was surprising at the time that easy (polynomial time) existence problems could lead to intractable counting problems, and it opened the door to hardness proofs for many other counting problems, primarily in graph theory. Beyond individual problems, several broad classifications of hard graph counting problems are now known. For instance, it is #P-complete to count k-colorings of a graph or determine the value of its Tutte polynomial at any argument of the polynomial outside of a small finite set of exceptions [26], and all problems of counting homomorphisms to a fixed directed acyclic graph are either #P-complete or polynomial [17]. However, in computational geometry, only a small number of isolated problems have been shown to be #P-complete or #P-hard. These include counting the vertices or facets of high-dimensional convex polytopes [31], computing the expected total length of the minimum spanning tree of a stochastic subset of three-dimensional points [28], and counting linear extensions of two-dimensional dominance partial orderings [15]. 1 See Sect. 2.2 for the definitions of #P and #P-completeness.
Editor in Charge: Kenneth Clarkson David Eppstein [email protected] 1
Computer Science Department, University of California, Irvine, USA
123
Discrete & Computational Geometry
Because of the rarity of complete problems in this area, other problems of counting geometric structures can only be inferred to be NP-hard, in cases for which constructing the structure is NP-hard [7,9,29,32,34]. There has been significant research on counting easy-to-construct non-crossing configurations in the plane, including matchings, simple polygons, spanning trees, triangulations, and pseudotriangulations; however, the complexity of these problems has remained undetermined. Research on these problems has instead focused on determining the number of configurations for special classes of point sets [8,20,27], bounding the number of configurations as a function of the number of points [1–4,10,16,23,36,39–42], developing exponential- or subexponential-time counting algorithms [6,7,12,13,33,45], or finding faster approximations [5,30]. In this paper we bring the two worlds of #P-completeness and counting non-crossing configurations together by proving the following theorem: Theorem 1.1 It is #P-complete to count the number of triangulations
Data Loading...
