Counting Triangulations and Other Crossing-Free Structures via Onion Layers

Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray

Research output: Contribution to journalArticlepeer-review

Abstract

Let P be a set of n points in the plane. A crossing-free structure on P is a straight-edge plane graph with vertex set P. Examples of crossing-free structures include triangulations and spanning cycles, also known as polygonalizations. In recent years, there has been a large amount of research trying to bound the number of such structures; in particular, bounding the number of (crossing-free) triangulations spanned by P has received considerable attention. It is currently known that every set of n points has at most O(30n) and at least Ω(2.43n) triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set P. In this paper, we develop a general technique for computing the number of crossing-free structures of an input set P. We apply the technique to obtain algorithms for computing the number of triangulations, matchings, and spanning cycles of P. The running time of our algorithms is upper-bounded by nO(k), where k is the number of onion layers of P. In particular, for k=O(1) our algorithms run in polynomial time. Additionally, we show that our algorithm for counting triangulations in the worst case over all k takes time O(3.1414n). [In the notations Ω(·),O(·), and Θ(·), we neglect polynomial terms and we just present the dominating exponential term.] Given that there are several well-studied configurations of points with at least Ω(3.47n) triangulations, and some even with Ω(8.65n) triangulations, our algorithm asymptotically outperforms any enumeration algorithm for such instances. We also show that our techniques are general enough to solve the Restricted-Triangulation-Counting-Problem, which we prove to be W[2]-hard in the parameter $$k$$k. This implies that in order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of crossing-free structures.

Original languageEnglish (US)
Pages (from-to)675-690
Number of pages16
JournalDiscrete and Computational Geometry
Volume53
Issue number4
DOIs
StatePublished - Jun 1 2015

Keywords

  • Algorithmic geometry
  • Counting algorithms
  • Crossing-free structures
  • Matchings
  • Spanning cycles
  • Spanning trees
  • Triangulations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Counting Triangulations and Other Crossing-Free Structures via Onion Layers'. Together they form a unique fingerprint.

Cite this