# Memory-Centric Computing

Onur Mutlu
_ETH Zürich_

###### Abstract

Modern computing systems are processor-centric. Data processing (i.e.,
computation) happens only in the processor (e.g., a CPU, GPU, FPGA, ASIC). As
such, data needs to be moved from where it is generated/captured (e.g.,
sensors) and stored (e.g., storage and memory devices) to the processor before
it can be processed. The processor-centric design paradigm greatly limits the
performance & energy-efficiency, as well as scalability & sustainability, of
modern computing systems. Many studies show that even the most powerful
processors and accelerators waste a large fraction (e.g., >60%) of their time
simply waiting for data and energy on moving data between storage/memory units
to the processor. This is so even though most of the hardware real estate of
such systems is dedicated to data storage and communication (e.g., many levels
of caches, DRAM chips, storage systems, and interconnects).

Memory-centric computing aims to enable computation capability in and near all
places where data is generated and stored. As such, it can greatly reduce the
large negative performance and energy impact of data access and data movement,
by fundamentally avoiding data movement and reducing data access latency &
energy. Many recent studies show that memory-centric computing can greatly
improve system performance and energy efficiency. Major industrial vendors and
startup companies have also recently introduced memory chips that have
sophisticated computation capabilities.

This talk describes promising ongoing research and development efforts in
memory-centric computing. We classify such efforts into two major fundamental
categories: 1) processing using memory, which exploits analog operational
properties of memory structures to perform massively-parallel operations in
memory, and 2) processing near memory, which integrates processing capability
in memory controllers, the logic layer of 3D-stacked memory technologies, or
memory chips to enable high-bandwidth and low-latency memory access to near-
memory logic. We show both types of architectures (and their combination) can
enable orders of magnitude improvements in performance and energy consumption
of many important workloads, such as graph analytics, databases, machine
learning, video processing, climate modeling, genome analysis. We discuss
adoption challenges for the memory-centric computing paradigm and conclude
with some research & development opportunities.

##  1 Memory-Centric Computing

Memory-centric computing (also called processing in memory, PIM) is a
processing paradigm where data processing is performed near and in devices
where data is generated (e.g., sensors) or stored (e.g., memory and storage
devices) [1]. This paradigm enables computing to be more efficient by offering
an alternative to modern systems, which overwhelmingly use the processor-
centric paradigm where data processing is performed only in the processor
(which can be a CPU, GPU, FPGA, ASIC in modern systems). Memory-centric
computing has several advantages over processor-centric computing. First, it
fundamentally reduces the data movement bottleneck [2], which plagues
processor-centric systems that have to move data to the processor before
processing it. Second, it enables low-latency and low-energy access to data by
reducing the distance between processing units and data storage & sensing
units. Third, it can exploit large amounts of parallelism present in modern
memory, storage, and sensor arrays to perform massively parallel (bit-level)
computation [3]. As such, memory-centric computing promises to improve both
performance and energy-efficiency at the same time.

Memory-centric computing systems can be categorized into two types [4, 1],
based on the fundamental way in which computation is performed: 1) processing
using memory (PuM), and 2) processing near memory (PnM). We briefly describe
these next and give examples from recent works. These two approaches can be
combined to obtain the best of both approaches.

###  1.1 Processing using Memory (PuM)

A memory device has analog operational properties that enable it to perform
(varying types and amounts of) computation. PuM exploits these properties to
perform computation using the memory device (including memory cells, bitlines,
wordlines, sensing structures, and peripheral circuitry). As such, the PuM
approach can enable computation without adding logic to perform computation
into a memory device, which makes it fundamentally different from modern
processor-centric systems as well as PnM systems that add such logic near or
in memory devices. PuM approach can be made more powerful by designing the
memory device to increase its capability to perform analog computation.

PuM approaches have been demonstrated in DRAM (e.g., [5, 6, 7, 8, 3, 9, 10]),
NVM (e.g., [11, 12, 13]), NAND flash (e.g., [14, 15]) and SRAM (e.g., [16,
17]) devices. For example, recent works [5, 18, 19] show that data copy and
initialization can be performed inside a DRAM chip by exploiting internal
connectivity in the DRAM chip, even in existing real DRAM chips that do not
explicitly support these operations. Latency of a 4KB data copy can be
improved by more than 11X and energy by 77X compared to a state-of-the-art
processor-centric solution. Recent works [6, 8, 18, 9] also show that bulk
bitwise operations (Majority, AND, OR, NOT) and true random number generation
[20, 21] can be performed in commodity DRAM chips with small modifications or
by violating timing parameters. Frameworks and compilers have been introduced
to implement any type of operation using such bulk bitwise computation
capability, with little effort required from the programmer [9]. Real NAND
flash memory chips can also perform bulk bitwise operations (AND, OR NOT, XOR)
using inherent operational properties of NAND flash cells and strings as well
as peripheral circuitry [14, 15]. Some emerging memory technologies are
capable of performing matrix-vector multiplication operations in the analog
domain due to their crossbar array structure [12, 13], and various test chips
have been designed to demonstrate this as proof-of-concept prototypes.

###  1.2 Processing near Memory (PnM)

PnM adds processing logic (similar to modern processors and accelerators)
close to or inside a memory device such that the distance between the
processing logic and memory device is much smaller than in processor-centric
systems. Such logic can be added to memory controllers, the logic layer of
3D-stacked memories, around peripheral circuitry in a memory chip, near memory
subarrays in a memory chip, etc. The closer the logic is to the data storage
parts of memory, the lower the amount of data movement. As such, PnM is not
fundamentally different from modern systems where processing logic and memory
structures are distinct, yet PnM greatly reduces the distance between them and
in more aggressive implementations places logic and memory together in a
tightly-integrated manner.

Many recent works (e.g., [22, 23, 24, 25]) have shown the benefits of the PnM
approach, by especially focusing on how various different types of
applications can be accelerated using such an approach with varying levels of
modifications to applications. For example, rewriting the entire application
and changing the programming model to execute graph analytics near memory can
greatly improve both performance and efficiency, by more than an order of
magnitude [22, 23]. Less intrusive PnM approaches offload specific functions
or instructions to near-memory logic [2, 26, 27, 28, 29, 30], with lower but
still large performance and energy benefits.

###  1.3 Real PIM Systems

Recently, several real DRAM-based PnM systems were introduced as commercial
systems or promising prototypes. The UPMEM company, for example, introduced a
system where DRAM chips contain a general-purpose multithreaded processor next
to each DRAM bank [31]. Several studies of the UPMEM system (e.g., [32, 33,
34, 35, 36]) demonstrate the benefits and tradeoffs of this first commercial
memory-centric system on various workloads and present benchmark suites and
libraries for it. These studies show large performance and energy benefits
when the workload is carefully designed to fit the constraints present in the
PnM system, which is limited in terms of the computation power within the
near-memory processors and the communication capability present between such
processors and the host CPU. These studies also indicate how future general-
purpose PnM systems can be improved to be much more powerful and effective.

Several major vendors developed specialized PnM systems targeted toward
machine learning applications and recommendation systems. For example, Samsung
introduced FIMDRAM [37], which is intended to accelerate floating-point based
matrix operations (with native support for FP multiply and accumulates) in a
DRAM chip. FIMDRAM incorporates processing units next to DRAM banks. To
accelerate similar applications, SK-Hynix introduced the AiM-DRAM system [38],
which also incorporates near-bank computation units. Two other PnM systems
were introduced by Alibaba [39] and Samsung/Meta [40] to accelerate
recommendation systems. The former modifies a DRAM chip to perform specialized
computation tailored towards recommendation inference. The latter includes a
processing buffer chip in a DRAM module that performs similarly specialized
computation on data coming from many DRAM chips surrounding it.

Systems where computation can be offloaded to FPGAs that are equipped with
high-bandwidth memory (HBM) also exist [41]. These systems can provide
significant performance and energy benefits on various applications (e.g.,
[41, 42]), including weather modeling and genome analysis.

###  1.4 Adoption Challenges

Even though real PIM systems exist, memory-centric computing is far from being
adopted in a widespread manner. To reach that level and thus realize the full
potential and benefits of memory-centric computing, a number of challenges
likely need to be solved. Many of these adoption challenges are common to PnM
and PuM systems. We briefly cover some of these challenges, as they constitute
important areas to investigate both in research and development of memory-
centric computing systems.

First, it is important to accurately and comprehensively demonstrate which
workloads and algorithms can benefit from memory-centric computing and by how
much. This can enable a larger momentum for adopting PIM systems. It is
especially critical to maximize benefits on important workloads. Second,
widespread adoption of PIM requires such systems to be easy to program [43],
which in turn requires support for seamless programming and compilation.
Third, system and security support is needed to enable high efficiency and
ease of use/programming. This wide topic includes support for data coherence
between PIM and other computation units (e.g., CPUs) [44, 45], synchronization
[46], virtual memory [29], multiprogramming and sharing of PIM computation
units, isolation between processes executing on PIM units, and communication
interfaces to access PIM units. Fourth, it is important to design runtimes and
compilation systems to decide what code should be executed in PIM units [47],
how data should be mapped to facilitate PIM execution, and how access control
and data sharing should be managed. Fifth, there is continual need for
infrastructures and benchmarks (e.g., [47, 19, 33, 34, 35, 48, 49]) that help
both hardware designers and software designers to accurately assess benefits,
tradeoffs, and feasibility of different types of memory-centric computing
systems. Finally, it is important to lower cost and demonstrate TCO benefits.

PuM systems have specific additional challenges due to their analog nature of
computation. These include how to tolerate circuit variation and noise, how to
ensure reliable operation, and how to enable computation on large memory
arrays for scalable performance. In addition, some PUM systems implemented
using memories that have endurance problems exacerbate lifetime and endurance
problems. Due to such challenges, we believe PuM systems are harder to adopt
in the short term even though their benefits can be fundamentally higher than
PnM systems.

###  1.5 Future Opportunities and Outlook

Memory-centric computing can enable balanced and efficient system designs
where computation and memory access are fundamentally balanced and the
processor-memory dichotomy is eliminated. These systems can provide greatly
higher performance and efficiency than existing processor-centric systems.
They can also enable potentially new applications and computing platforms.
However, as with any new paradigm, memory-centric computing systems pose
significant adoption challenges. We believe the processor-centric mindset that
is ingrained in essentially every decision made in modern computing systems is
likely the largest adoption challenge memory-centric systems face. We conclude
that the future of memory-centric computing is very bright, but there is a lot
more exciting research and development to do.

## References

  * [1] O. Mutlu _et al._ , “A Modern Primer on Processing in Memory,” _Emerging Computing: From Devices to Systems_ , 2021, https://arxiv.org/pdf/2012.03112.pdf.
  * [2] A. Boroumand _et al._ , “Google Workloads for Consumer Devices: Mitigating Data Movement Bottlenecks,” in _ASPLOS_ , 2018.
  * [3] V. Seshadri and O. Mutlu, “In-DRAM Bulk Bitwise Execution Engine,” _arXiv_ , 2020.
  * [4] O. Mutlu _et al._ , “Processing Data Where It Makes Sense: Enabling In-Memory Computation,” _MicPro_ , 2019.
  * [5] V. Seshadri _et al._ , “RowClone: Fast and Energy-Efficient In-DRAM Bulk Data Copy and Initialization,” in _MICRO_ , 2013\.
  * [6] V. Seshadri _et al._ , “Fast Bulk Bitwise AND and OR in DRAM,” _CAL_ , 2015.
  * [7] V. Seshadri _et al._ , “Buddy-RAM: Improving the Performance and Efficiency of Bulk Bitwise Operations Using DRAM,” _arXiv_ , 2016\.
  * [8] V. Seshadri _et al._ , “Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology,” in _MICRO_ , 2017.
  * [9] N. Hajinazar _et al._ , “SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM,” in _ASPLOS_ , 2021.
  * [10] J. D. Ferreira _et al._ , “pLUTo: Enabling Massively Parallel Computation in DRAM via Lookup Tables,” in _MICRO_ , 2022.
  * [11] S. Li _et al._ , “Pinatubo: A processing-in-memory architecture for bulk bitwise operations in emerging non-volatile memories,” in _DAC_ , 2016.
  * [12] A. Shafiee _et al._ , “ISAAC: A Convolutional Neural Network Accelerator with In-situ Analog Arithmetic in Crossbars,” in _ISCA_ , 2016.
  * [13] P. Chi _et al._ , “PRIME: A Novel Processing-In-Memory Architecture for Neural Network Computation In ReRAM-Based Main Memory,” in _ISCA_ , 2016\.
  * [14] J. Park _et al._ , “Flash-Cosmos: In-Flash Bulk Bitwise Operations Using Inherent Computation Capability of NAND Flash Memory,” in _MICRO_ , 2022\.
  * [15] C. Gao _et al._ , “ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory based SSDs,” in _MICRO_ , 2021.
  * [16] M. Kang _et al._ , “An Energy-Efficient VLSI Architecture for Pattern Recognition via Deep Embedding of Computation in SRAM,” in _ICASSP_ , 2014\.
  * [17] S. Aga _et al._ , “Compute Caches,” in _HPCA_ , 2017.
  * [18] F. Gao _et al._ , “ComputeDRAM: In-Memory Compute Using Off-the-Shelf DRAMs,” in _MICRO_ , 2019.
  * [19] A. Olgun _et al._ , “PiDRAM: A Holistic End-to-end FPGA-based Framework for Processing-in-DRAM",” _TACO_ , 2023.
  * [20] J. Kim _et al._ , “D-RaNGe: Using Commodity DRAM Devices to Generate True Random Numbers with Low Latency and High Throughput,” in _HPCA_ , 2019\.
  * [21] A. Olgun _et al._ , “QUAC-TRNG: High-Throughput True Random Number Generation Using Quadruple Row Activation in Commodity DRAMs,” in _ISCA_ , 2021.
  * [22] J. Ahn _et al._ , “A Scalable Processing-in-Memory Accelerator for Parallel Graph Processing,” in _ISCA_ , 2015.
  * [23] M. Besta _et al._ , “SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems,” in _MICRO_ , 2021.
  * [24] I. Fernandez _et al._ , “NATSA: A Near-Data Processing Accelerator for Time Series Analysis,” in _ICCD_ , 2020.
  * [25] N. M. Ghiasi _et al._ , “GenStore: A High-Performance and Energy-Efficient In-Storage Computing System for Genome Sequence Analysis,” in _ASPLOS_ , 2022.
  * [26] K. Hsieh _et al._ , “Transparent Offloading and Mapping (TOM): Enabling Programmer-Transparent Near-Data Processing in GPU Systems,” in _ISCA_ , 2016.
  * [27] A. Boroumand _et al._ , “Google Neural Network Models for Edge Devices: Analyzing and Mitigating Machine Learning Inference Bottlenecks,” in _PACT_ , 2021.
  * [28] J. Ahn _et al._ , “PIM-Enabled Instructions: A Low-Overhead, Locality-Aware Processing-in-Memory Architecture,” in _ISCA_ , 2015.
  * [29] K. Hsieh _et al._ , “Accelerating Pointer Chasing in 3D-Stacked Memory: Challenges, Mechanisms, Evaluation,” in _ICCD_ , 2016.
  * [30] A. Boroumand _et al._ , “Polynesia: Enabling Effective Hybrid Transactional Analytical Databases with Specialized Hardware Software Co-Design,” in _ICDE_ , 2022.
  * [31] F. Devaux, “The True Processing In Memory Accelerator,” in _Hot Chips_ , 2019.
  * [32] J. Gómez-Luna _et al._ , “Benchmarking Memory-Centric Computing Systems: Analysis of Real Processing-In-Memory Hardware,” in _IGSC_ , 2021.
  * [33] J. Gómez-Luna _et al._ , “Benchmarking a New Paradigm: Experimental Analysis and Characterization of a Real Processing-in-Memory System,” _IEEE Access_ , 2022.
  * [34] C. Giannoula _et al._ , “Towards Efficient Sparse Matrix Vector Multiplication on Real Processing-in-Memory Architectures,” in _SIGMETRICS_ , 2022.
  * [35] J. Gomez-Luna _et al._ , “Evaluating Machine Learning Workloads on Memory-Centric Computing Systems,” in _ISPASS_ , 2023.
  * [36] S. Diab _et al._ , “A Framework for High-throughput Sequence Alignment using Real Processing-in-Memory Systems",” _Bioinformatics_ , 2023.
  * [37] Y.-C. Kwon _et al._ , “25.4 A 20nm 6GB Function-In-Memory DRAM, Based on HBM2 with a 1.2 TFLOPS Programmable Computing Unit Using Bank-Level Parallelism, for Machine Learning Applications,” in _ISSCC_ , 2021.
  * [38] S. Lee _et al._ , “A 1ynm 1.25V 8Gb, 16Gb/s/pin GDDR6-based Accelerator-in-Memory supporting 1TFLOPS MAC Operation and Various Activation Functions for Deep-Learning Applications,” in _ISSCC_ , 2022.
  * [39] D. Niu _et al._ , “184QPS/W 64Mb/mm2 3D Logic-to-DRAM Hybrid Bonding with Process-Near-Memory Engine for Recommendation System,” in _ISSCC_ , 2022\.
  * [40] L. Ke _et al._ , “Near-Memory Processing in Action: Accelerating Personalized Recommendation with AxDIMM,” _IEEE Micro_ , 2021.
  * [41] G. Singh _et al._ , “FPGA-based Near-Memory Acceleration of Modern Data-Intensive Applications,” _IEEE Micro_ , 2021.
  * [42] G. Singh _et al._ , “NERO: A Near High-Bandwidth Memory Stencil Accelerator for Weather Prediction Modeling,” in _FPL_ , 2020.
  * [43] S. Ghose _et al._ , “Processing-in-Memory: A Workload-Driven Perspective,” _IBM JRD_ , 2019.
  * [44] A. Boroumand _et al._ , “CoNDA: Efficient Cache Coherence Support for near-Data Accelerators,” in _ISCA_ , 2019.
  * [45] A. Boroumand _et al._ , “LazyPIM: An Efficient Cache Coherence Mechanism for Processing-in-Memory,” _CAL_ , 2016.
  * [46] C. Giannoula _et al._ , “SynCron: Efficient Synchronization Support for Near-Data-Processing Architectures,” in _HPCA_ , 2021\.
  * [47] G. F. Oliveira _et al._ , “DAMOV: A New Methodology and Benchmark Suite for Evaluating Data Movement Bottlenecks,” _IEEE Access_ , 2021.
  * [48] Y. Kim _et al._ , “Ramulator: A Fast and Extensible DRAM Simulator,” _CAL_ , 2015.
  * [49] G. Singh _et al._ , “NAPEL: Near-memory Computing Application Performance Prediction via Ensemble Learning,” in _DAC_ , 2019.


lemmatheorem lemma corollarytheorem corollary definitiontheorem definition

# Counting Polygon Triangulations is Hard

David Eppstein
Computer Science Department, University of California, Irvine

###### Abstract

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

##  1 Introduction

In 1979, Leslie Valiant published his proof that it is
$\\#\mathsf{P}$-complete to compute the permanent of a 0–1 matrix, or
equivalently to count the perfect matchings of a bipartite graph [44].111See
subsection 2.2 for the definitions of $\\#\mathsf{P}$ and
$\\#\mathsf{P}$-completeness. 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 $\\#\mathsf{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 [25],
and all problems of counting homomorphisms to a fixed directed acyclic graph
are either $\\#\mathsf{P}$-complete or polynomial [19].

However, in computational geometry, only a small number of isolated problems
have been shown to be $\\#\mathsf{P}$-complete or $\\#\mathsf{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 [17]. Because of the
rarity of complete problems in this area, other problems of counting geometric
structures can only be inferred to be $\mathsf{NP}$-hard, in cases for which
constructing the structure is $\mathsf{NP}$-hard [5, 9, 34, 32, 29]. 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 [22, 8, 27], bounding the number of configurations as a
function of the number of points [2, 4, 42, 40, 18, 41, 1, 36, 3, 39, 23, 10],
developing exponential- or subexponential-time counting algorithms [12, 7, 45,
5, 33, 13], or finding faster approximations [6, 30].

In this paper we bring the two worlds of $\\#\mathsf{P}$-completeness and
counting non-crossing configurations together by proving the following
theorem:

######  Theorem 1.

It is $\\#\mathsf{P}$-complete to count the number of triangulations of a
given polygon.

The polygons constructed in our hardness proof have vertices with integer
coordinates of polynomial magnitude. Necessarily, they have holes, as it is
straightforward to count the triangulations of a simple polygon in polynomial
time by dynamic programming [21, 35, 16]. Our proof strategy is to develop a
polynomial-time counting reduction from the problem of counting independent
sets in planar graphs (here the independent sets are not necessarily maximum
nor maximal), which was proved $\\#\mathsf{P}$-complete by Vadhan [43] (see
also [46]). We reduce counting independent sets in planar graphs to counting
maximum-size non-crossing subsets of a special class of line segment
arrangements, which we in turn reduce to counting triangulations.

##  2 Preliminaries

###  2.1 Polygons and triangulation

A _planar straight-line graph_ consists of finitely many closed line segments
in the Euclidean plane, disjoint except for shared endpoints. The endpoints of
these segments can be interpreted as the vertices, and the segments as the
edges, of an undirected graph drawn with straight edges and no crossings in
the plane. The _faces_ of the planar straight-line graph are the connected
components of its complement (that is, maximal connected subsets of the plane
that are disjoint from the segments of the graph). In any planar straight-line
graph, exactly one unbounded face extends beyond the bounding box of the
segments; all other faces are bounded. A segment of the graph forms a _side_
of a face if the interior of the segment intersects the topological closure of
the face. As with any graph, a planar straight-line graph is $d$-regular if
each of its vertices is incident to exactly $d$ line segments. If $G$ is any
graph, we denote the sets of vertices or edges of $G$ by $V(G)$ or $E(G)$
respectively, and the numbers of vertices or edges by $|V(G)|$ or $|E(G)|$
respectively.

For the purposes of this paper, we define a _polygon_ $P$ to be a 2-regular
planar straight-line graph in which there is a bounded face $\phi$ whose sides
are all the segments of $P$. If $\phi$ exists, it is uniquely determined from
$P$. We call $\phi$ the _interior_ of $P$. The connected components of the
graph are necessarily simple cycles of line segments, exactly one of which
separates $\phi$ from the unbounded face. If there is more than one connected
component of the graph, we call the other components _holes_ , and if there
are no holes we call $P$ a _simple polygon_. We denote the number of vertices
(or edges) of the polygon by $|P|$.

We define a _triangulation_ of a polygon $P$ to be a planar straight-line
graph consisting of the edges of $P$ and added segments interior to $P$, all
of whose vertices are vertices of $P$, partitioning the interior of $P$ into
three-sided faces. As is well known, every polygon has a triangulation. A
triangulation of a polygon $P$ can be found in time $O(|P|\log|P|)$, for
instance by constrained Delaunay triangulation, and this can be improved to
$O(|P|\log h)$ for polygons with $h$ holes [11]. The known exponential or sub-
exponential algorithms for counting triangulations of point sets [7, 33] can
be adapted to count triangulations of polygons in the same time bounds.

###  2.2 Counting complexity

The complexity class $\\#\mathsf{P}$ and the notion of
$\\#\mathsf{P}$-completeness were introduced by Valiant [44]. $\\#\mathsf{P}$
is defined as the class of functional algorithmic problems for which the
desired output counts the accepting paths of some nondeterministic polynomial-
time Turing machine.

######  Lemma .

Computing the number of triangulations of a polygon is in $\\#\mathsf{P}$.

###### Proof.

The output is the number of accepting paths of a nondeterministic polynomial-
time Turing machine that guesses the set of edges in the triangulation, and
verifies that these edges form a triangulation of the input. ∎

$\\#\mathsf{P}$-hardness and $\\#\mathsf{P}$-completeness are defined using
reductions, polynomial-time transformations from one problem $X$ (typically
already known to be hard) to another problem $Y$ that we wish to prove hard.
Three types of reduction are in common use for this purpose:

  * •

_Turing reductions_ consist of an algorithm for solving problem $X$ in
polynomial time given access to an oracle for solving problem $Y$.

  * •

_Polynomial-time counting reductions_ consist of two polynomial-time
transformations: a transformation $\sigma$ that transforms inputs to $X$ into
inputs to $Y$, and a second transformation $\tau$ that transforms outputs of
$Y$ back to outputs of $X$. The reduction is valid if, for every input $\chi$
to problem $X$, $\tau(Y(\sigma(\chi)))=X(\chi)$.

  * •

_Parsimonious reductions_ consist of a polynomial-time transformation from
inputs of $X$ to inputs of $Y$ that preserve the exact solution value.

A problem $Y$ is defined to be $\\#\mathsf{P}$-hard for a given class of
reductions if every problem $X$ in $\\#\mathsf{P}$ has a reduction to $Y$. $Y$
is $\\#\mathsf{P}$-complete if, in addition, $Y$ is itself in $\\#\mathsf{P}$.
Composing two reductions of the same type produces another reduction, so we
will generally prove $\\#\mathsf{P}$-hardness or $\\#\mathsf{P}$-completeness
by finding a single reduction from a known-hard problem and composing it with
the reductions from everything else in $\\#\mathsf{P}$ to that known-hard
problem.

The reductions that we construct in this work will be polynomial-time counting
reductions. However, we rely on earlier work on $\\#\mathsf{P}$-completeness
of graph problems that uses the weaker notion of Turing reductions. Therefore,
we will prove that our geometric problems are $\\#\mathsf{P}$-complete under
Turing reductions. If the graph-theoretic results are strengthened to use
counting reductions (and in particular if either counting maximum independent
sets in regular planar graphs or counting independent sets in planar graphs is
$\\#\mathsf{P}$-complete under counting reductions) then the same
strengthening will apply as well to counting triangulations. For the remainder
of this paper, however, whenever we refer to $\\#\mathsf{P}$-hardness or
$\\#\mathsf{P}$-completeness, it will be under Turing reductions.

###  2.3 Counting independent sets

Vadhan [43] proved that it is $\\#\mathsf{P}$-complete to count independent
sets in planar graphs. Although not necessary for our results, it will
simplify our exposition to use a stronger form of this result by Xia, Zhang,
and Zhao [46]. They proved that it is also $\\#\mathsf{P}$-complete to count
the vertex covers in a connected 3-regular bipartite planar graph (subsets of
vertices that touch all edges). A set of vertices is a vertex cover if and
only if its complement is an independent set, so it immediately follows that
it is also $\\#\mathsf{P}$-complete to count independent sets in 3-regular
planar graphs.

##  3 Red–blue arrangements

In this section we define and prove hard a counting problem that will be an
intermediate step in our hardness proof for triangulations. It involves
counting maximum-size non-crossing subsets of certain special line segment
arrangements. Counting maximum-size non-crossing subsets of arbitrary line
segment arrangements can easily be shown to be hard: It follows from the
hardness of counting maximum independent sets in planar graphs [43] and from
the proof of Scheinerman’s conjecture that every planar graph can be
represented as an intersection graph of line segments [37, 14]. So the
significance of the reduction that we describe in this section is that it
provides arrangements with a highly constrained form, a form that will be
useful in our eventual reduction to counting triangulations.

######  Definition .

We define a _red–blue arrangement_ to be a collection of finitely many line
segments in the plane (specified by the Cartesian coordinates of their
endpoints) with the following properties:

  * •

Each line segment is assigned a color, either red or blue.

  * •

Each intersection point of two segments is a proper crossing point of exactly
two segments.

  * •

Each blue segment is crossed by exactly two other segments, both red.

  * •

Each red segment is crossed by exactly three other segments, in the order
blue–red–blue.

  * •

The union of the segments forms a connected subset of the plane.

See the right side of Figure 1 for an example. We will be interested in the
maximum-size non-crossing subsets of such an arrangement: sets of as many
segments as possible, no two of which cross.

In a red–blue arrangement, consider the graph whose vertices represent line
segments and whose edges represent bichromatic crossings (crossings between a
red segment and a blue segment). Then this graph is a disjoint union of
cycles, each of which has even length with vertices alternating between red
and blue. We call the cycles of this graph _alternating cycles_ of the
arrangement.

######  Lemma .

Every red–blue arrangement has equal numbers of red and blue segments. If
there are $r$ red segments (and therefore also $r$ blue segments), the
maximum-size non-crossing subsets of the arrangement all have exactly $r$
segments. Within each alternating cycle of the arrangement, a maximum-size
non-crossing subset must use a monochromatic subset of the cycle (either all
the red segments of the cycle, or all the blue segments of the cycle).

###### Proof.

The equal numbers of red and blue segments in the whole arrangement follow
from the decomposition of the arrangement into alternating cycles and the
equal numbers within each cycle. Within a single cycle, there are exactly two
maximum-size non-crossing subsets, the subsets of red and of blue segments,
each of which uses exactly half of the segments of the cycle. Therefore, no
non-crossing subset of the whole arrangement can include more than $r$
segments (half of the total), and a non-crossing subset that uses exactly $r$
segments must be monochromatic within each alternating cycle. There exists at
least one non-crossing subset of exactly $r$ segments, namely the set of blue
segments. ∎

Given a connected 3-regular planar graph $G$, we will construct a red–blue
arrangement $A_{G}$ from it. In overview, our construction begins by finding a
straight-line drawing of $G$. We then replace each vertex $v$ of $G$ by a
twelve-segment alternating cycle (Figure 1, lower left). Each edge of $G$
incident to $v$ will have two red segments on either side of it, within the
two faces bounded by that edge, and these segments form the six red segments
of the alternating cycle. Three blue segments, drawn near $v$ within the three
faces incident to $v$, connect pairs of red segments within each face. Another
three blue segments cross the three edges incident to $v$ (which are not
themselves part of the arrangement) and connect the two red segments on either
side of the edge.

Figure 1: Transformation from a 3-regular planar graph $G$ to a red–blue
arrangement. Left: gadgets for transforming edges and vertices of $G$ into red
and blue segments that will form parts of the arrangement. Right: an example
of the complete red–blue arrangement for the graph of a triangular prism.

In this way, each edge $uv$ of $G$ will have four red segments near it (two on
each side from each of its two endpoints) and two blue segments crossing it
(one from each endpoint). We arrange these segments so that, on each side of
$uv$, the two red segments cross, and there are no other crossings except
those in the alternating cycles (Figure 1, upper left). An example of the
whole red–blue arrangement produced by these rules is shown in Figure 1,
right.

In order to apply this drawing method as part of a counting reduction, it
needs to be constructable in polynomial time, using coordinates that can be
represented by binary numbers with a polynomial number of bits of precision.
We will show more strongly that the coordinates themselves can be chosen to
have polynomial magnitude (needing only a logarithmic number of bits of
precision). Thus, we now describe in more detail the steps of our
construction.

The first of these steps is to find a planar straight line drawing of the
given planar graph $G$. We use known methods to find a planar straight line
drawing of $G$ within an integer grid of size $|V(G)|\times|V(G)|$, in linear
time [38, 15].

Figure 2: Part of a graph $G$ including two vertices $u$ and $v$ (small yellow
circles), the edge $uv$ between them, parts of other adjacent edges (black),
the associated guide disks (large yellow circles), and a placement of red and
blue segment endpoints within the guide disks.

After constructing the drawing of $G$, the next step of our construction is to
place “guide disks” in the drawing, two along each edge and three near each
vertex (Figure 2). These disks will each contain two endpoints of disjoint red
segments in our eventual red-blue segment arrangement, and both endpoints of a
blue segment that crosses these two red segments. We center the two guide
disks on each edge at points $2/5$ and $3/5$ of the way between the two
endpoints of the edge. At each vertex $v$, three edges of $G$ are incident,
forming the boundaries of three wedges between them. We place the three guide
disks on the angle bisectors of these wedges, centered at a distance from $v$
equal to $1/5$ of the smallest nonzero distance from $v$ to any other edge or
vertex of $G$. We choose all of these guide disks to have equal radii $\rho$
(depending on $|V(G)|$). We set $\rho$ to be small enough to meet the
following constraints:

  * •

No two guide disks intersect each other.

  * •

A guide disk on an edge of $G$ does not intersect any other edge or vertex of
$G$.

  * •

A guide disk near a vertex of $G$ does not intersect any edge or vertex of
$G$.

  * •

For every edge $uv$ of $G$, there does not exist a line segment in the plane
that intersects the two guide disks on $uv$ and a third guide disk in one of
the four wedges bounded by $uv$.

######  Lemma .

There exists a radius $\rho=\Theta(1/|V(G)|^{3})$ that satisfies all of the
constraints above.

###### Proof.

Each two vertices in $G$ are at least at unit distance, because $G$ is on a
grid. The distance between each edge and non-incident vertex of $G$ is
$\Omega(1/|V(G)|)$, because the convex hull of the edge and vertex has area
$\Omega(1)$ (by Pick’s formula) and diameter $O(|V(G)|)$. Each two incident
edges form an angle of $\Omega(1/|V(G)|^{2})$, because they form a triangle of
area $\Omega(1)$ and diameter $O(|V(G)|)$ and because the area of a triangle
is proportional to the product of its squared diameter with its sharpest
angle. So, for each guide disk associated with a vertex $v$, the distance of
the disk center from $v$ is $\Omega(1/|V(G)|)$, and it will avoid intersecting
the two nearby edges forming an angle of $\Omega(1/|V(G)|^{2})$) as long as
$\rho$ is a sufficiently small constant multiple of $1/|V(G)|^{3}$. The same
bound suffices to achieve all of the instances of the first three constraints.
It remains to consider the final constraint.

This constraint may equivalently be stated as requiring the height of the
triangle formed by certain triples of guide disk centers, above the longest
edge of the triangle to be at least $2\rho$. In these triangles, for a triple
of disk centers associated with vertex $u$ and edge $uv$, the center near $u$
has height $\Omega(1/|V(G)|^{3})$ above line $uv$, which contains one of the
sides of the triangle. But in this triangle, all three edges have lengths
within a constant factor of each other, so all heights are also within a
constant factor of each other and are all $\Omega(1/|V(G)|^{3})$. So when
$\rho$ is a sufficiently small constant multiple of $1/|V(G)|^{3}$, the last
constraint is also satisfied. ∎

We must next show how to choose the endpoints of the red and blue segments
within each guide disk. To do so, we expand our drawing of $G$ (and its guide
disks) by a factor of $\Theta(|V(G)|^{3})$, enough to ensure that each guide
disk contains an $8\times 8$ grid of points. We observe that (because of the
small size of the guide disks relative to their distance apart) the angles of
each red segment are known to within an additive error of $O(1/|V(G)|^{3})$
regardless of where in their guide disks their endpoints are placed.
Additionally, the angle between any two red segments that leave the same guide
disk is $\Omega(1/|V(G)|^{2})$, again regardless of where in their guide disks
the segments are placed. We choose the endpoints of segments within each guide
disk independently, using the following lemma.

######  Lemma .

There exists a constant $\delta$ such that, for every two given slopes
$\Theta_{1}$ and $\Theta_{2}$ and every $8\times 8$ grid of points there exist
two rays and a line segment with the following properties:

  * •

One ray has slope $\Theta_{1}$ and the other has slope $\Theta_{2}$.

  * •

Both rays have their endpoint in the grid, and the line segment has both
endpoints in the grid.

  * •

The two rays are disjoint from each other, and both are crossed by the line
segment.

  * •

If the angles of the rays are continuously rotated by at most $\delta$ (while
not passing through the same angle as each other) the rays remain disjoint
from each other and crossed by the segment.

Figure 3: Case analysis for Section 3. For any two given slopes we can find a
grid of size at most $8\times 8$, and two disjoint (red) rays with those
slopes, having endpoints within the grid and crossed by a blue segment with
both endpoints in the grid, such that any sufficiently-small rotation of the
red rays does not change this crossing pattern. Left: two slopes that are
within $45^{\circ}$ of opposite directions on a coordinate axes;. Center: two
slopes that are within $45^{\circ}$ of the same direction on a coordinate
axis. Right: two slopes that are close to forming a right angle. The left and
middle cases also occur rotated by $45^{\circ}$, but these rotations still fit
within an $8\times 8$ grid.

###### Proof.

We may assume without loss of generality that the given grid is axis-aligned.
Some of the cases in our case analysis will instead use a grid that is rotated
by $45^{\circ}$ from the coordinate axes; such a grid can be found as a subset
of the given grid points, forming a subgrid with spacing larger by a factor of
$\sqrt{2}$.

If $\Theta_{1}$ and $\Theta_{2}$ are within $45^{\circ}$ of opposite
coordinate axes, or both within $45^{\circ}$ of opposite directions along a
line of slope $\pm 1$, we may use either the placement of red rays and blue
segment shown in Figure 3 (left), or its rotation by a multiple of
$45^{\circ}$ within a rotated subgrid. The grid placement shown uses a
$3\times 8$ subgrid of the given $8\times 8$ grid, while the rotated placement
fits within an $8\times 8$ axis-aligned grid (the bounding box of the rotated
version of the blue segment). The red wedges in the figure show regions within
which the two rays may rotate while preserving the correctness of the
construction; note that they span an angle greater than $45^{\circ}$ from the
horizontal axis in the figure. We may take $\delta$ in this case to be half of
the amount by which they are greater than $45^{\circ}$.

If $\Theta_{1}$ and $\Theta_{2}$ are both within $45^{\circ}$ of the same
direction along a coordinate axis, or along a line of slope $\pm 1$, we may
use the placement of red rays and blue segment shown in Figure 3 (center) or
its rotation by a multiple of $45^{\circ}$. The unrotated case fits within a
$2\times 5$ grid, and the rotated case fits within a $5\times 5$ grid (the
bounding box of the rotated version of the blue segment). Again, the wedges
span an angle greater than $45^{\circ}$ and we may take $\delta$ to be half of
the amount by which they are greater.

In the remaining case, if we partition the circle of directions of rays into
eight arcs spanning angles of $45^{\circ}$ by splitting it at the directions
of coordinate axes and lines of slope $\pm 1$, then $\Theta_{1}$ and
$\Theta_{2}$ must belong to arcs that are at right angles to each other. In
this case, we may use the placement of red rays and blue segment shown in
Figure 3 (right) or its rotation by a multiple of $90^{\circ}$. This case fits
within a $3\times 8$ grid. Again, the red wedges cover a greater range of
angles than the $45^{\circ}$ arcs that $\Theta_{1}$ and $\Theta_{2}$ belong
to, and we may take $\delta$ to be half of the amount by which they are
greater. ∎

By choosing segment endpoints in this way within each guide disk, we ensure
that the red and blue segments cross each other in the pattern described
earlier. This produces an alternating 6-cycle of red and blue segments around
each vertex. The cycles for adjacent vertices cross each other twice.

The next lemma shows that the construction of $A_{G}$ from $G$ is a
parsimonious reduction from independent sets to maximum non-crossing subsets,
and moreover that the size of an independent set can be determined from the
colors in the corresponding maximum non-crossing subset.

######  Lemma .

Let $G$ be a connected 3-regular planar graph, and let $A_{G}$ be constructed
from $G$ as above. Then the independent sets of $G$ correspond one-for-one
with the maximum-size non-crossing subsets of $A_{G}$, with an independent set
having size $k$ if and only if the corresponding non-crossing subset has
exactly $6k$ red segments.

###### Proof.

Given an independent set $Z$ in $G$, one can construct a non-crossing subset
of $A_{G}$ of size $6|V(G)|$, with $6|Z|$ red segments, by choosing all the
red segments in the alternating cycles around members of $Z$, and all the blue
segments in the remaining alternating cycles. Because $Z$ includes no two
adjacent vertices, the subsets chosen in this way will be non-crossing. $Z$
can be recovered as the set of vertices from which we used red segments of
alternating cycles, so the correspondence from independent sets to non-
crossing subsets constructed in this way is one-to-one.

By Section 3, these non-crossing subsets have maximum size. By the same lemma,
every maximum-size non-crossing subset consists of red segments in the
alternating cycles of some vertices of $G$ and blue segments in the remaining
alternating cycles. No two adjacent vertices of $G$ can have their red
segments chosen as that would produce a crossing, so there are no maximum-size
non-crossing subsets other than the ones coming from independent sets of $G$.
∎

This leads to the main result of this section:

######  Lemma .

It is $\\#\mathsf{P}$-complete to compute the number of maximum-size non-
crossing subsets of a red–blue arrangement $A$.

###### Proof.

The problem is clearly in $\\#\mathsf{P}$, as the number of these subsets
equals the number of accepting paths in a nondeterministic polynomial-time
Turing machine that nondeterministically chooses a subset of segments of the
arrangement, verifies that no two of the chosen segments cross each other,
verifies that the number of chosen segments is half of the total number of
segments, and accepts only if both of these things are true. By Section 3, the
construction of the red–blue arrangement $A_{G}$ from a 3-regular planar graph
$G$ is a parsimonious reduction from the known $\\#\mathsf{P}$-complete
problem of counting independent sets in 3-regular planar graphs. ∎

The arrangement constructed by this reduction has integer coefficients of
magnitude $O(|V(G)|^{4})$. Here, one factor of $|V(G)|$ comes from the
$|V(G)|\times|V(G)|$ grid on which we drew the planar graph $G$, and the
remaining factor of $O(|V(G)|^{3})$ comes from the expansion needed to ensure
that each guide disk contains an $8\times 8$ grid of integer points.

##  4 Reduction to counting triangulations

In this section we describe our reduction from line segment arrangements to
polygons. The rough idea is to thicken each segment of the given red–blue
arrangement to a rectangle with rounded ends, and form the union of these
rectangles. In the part of the polygon formed from each segment, many more
triangulations will use diagonals running end-to-end along the segment than
triangulations that do not, causing most triangulations to correspond to sets
of diagonals from a maximum-size non-crossing subset of the arrangement. With
a careful choice of the shapes of the thickened segments in this construction,
we can recover the number of maximum-size non-crossing subsets of the
arrangement from the number of triangulations.

###  4.1 From segments to polygons

Figure 4: Polygonal gadgets for replacing the red segments (top) and blue
segments (bottom) of a red–blue arrangement

The gadgets that we use to replace the red and blue segments of a red–blue
arrangement are shown (not to scale) in Figure 4. The top part of the figure
shows the gadget used to replace a single red segment, and the bottom part of
the figure shows the gadget used to replace a single blue segment. These
gadgets resemble the cross-section of a telescope, and we have named their
parts accordingly. Each gadget consists of $O(1)$ vertices spaced along two
convex curves, which we call the tube. These two curves bend slightly outwards
from each other, but both remain close to the center line of the gadget.
Consecutive pairs of points are connected to each other along the tube,
leaving either three gaps (for red segments) or two gaps (for blue segments)
where other segments of the arrangement cross the given segment. The two
vertices on each side of each gap are shared with the gadget for the crossing
segment.

At the ends of the tubes, the two convex curves are connected to each other by
two concave curves (the lenses of the gadget), each containing larger numbers
of vertices that are connected consecutively to each other without gaps. Each
blue lens has some number $a$ of vertices, and each red lens has some larger
number $a+b$ of vertices, where $a$ and $b$ are both positive integers to be
determined later as a function of the number of segments in the arrangement.
The key geometric properties of these gadgets are:

P1.

Each gadget forms a collection of polygonal chains whose internal vertices
(the vertices that are not the end-point of any of the chains) are not part of
any other gadget and whose endpoints are part of exactly one other gadget. The
union of all the gadgets of the arrangement forms a single polygon (with
holes).

P2.

Each vertex of the lens at one end of the gadget is visible within the polygon
to each vertex of the lens at the other end of the gadget, and to each vertex
of the tube of the gadget, but not to any vertices of its own lens that it is
non-adjacent to.

P3.

For each pair of points that are visible to each other there is a gadget
containing both of them. (This is not an automatic property of the gadgets as
drawn, but can be achieved by making the gadgets sufficiently narrow relative
to the spacing of points along their tubes, depending on the angles at which
different segments cross each other.)

Figure 5: A red–blue arrangement $A$ (thick colored segments) and the polygon
$P_{A}$ (shaded region with thin outlines) obtained from it by replacing its
segments by gadgets (schematic view, not to scale). $P_{A}$ has three holes
(unshaded regions entirely surrounded by $P_{A}$): a non-convex region below
the upper blue gadget, a central convex hexagon, and another non-convex region
above the lower blue gadget.

######  Definition .

We denote by $P_{A}$ any polygon obtained by replacing each segment of a
red–blue arrangement $A$ by a gadget, obeying properties P1, P2, and P3. For
any gadget $S$, we let $\Pi_{S}$ be the polygon formed by intersecting $P_{A}$
with the convex hull of $S$. $\Pi_{S}$ connects the endpoints of the polygonal
chains of $S$ into a single polygon in the obvious way.

Figure 5 gives an example of a red–blue arrangement $A$ and its corresponding
polygon $P_{A}$, drawn approximately and schematically (not to scale). To
analyze the magnitudes of the coordinates needed to carry out this
construction, let $\mu$ denote the maximum magnitude of the integer
coordinates in the given arrangement $A$, let $\nu$ denote the sharpest angle
at which two segments of $A$ cross each other, and let $\xi$ denote the
minimum distance between two crossing points or endpoints of the same segment
of $A$. For instance, for the arrangement generated by the reduction from
planar graphs to red-blue arrangements of Section 3, we have
$\mu=O(|V(G)|^{4})$, as discussed at the end of subsection 2.3. We also have
$\nu=\Omega(1/|V(G)|^{4})$: the crossing angles between red and blue segments
are described by the case analysis of Section 3, and are all $\Omega(1)$, so
the sharpest possible crossings are those between two red segments. Each red
segment has one endpoint within a guide disk of radius $O(1)$ centered on a
point in an edge of $G$, and forms an angle with that edge large enough to be
disjoint from the other guide disk; since the length of the edge is
$O(|V(G)|^{4})$, the angle between the red segment and the edge must be
$\Omega(1/|V(G)|^{4})$. Any two crossing red segments have angles of opposite
signs to the edge they both correspond to, of at least this magnitude, so
their crossing angle is $\Omega(1/|V(G)|^{4})$. And we have $\xi=\Omega(1)$
because all nearby crossing pairs occur within one of the cases of Section 3,
which all have constant separation for their two crossings.

We will scale $A$ by a large integer factor so that the integer grid forms a
fine subgrid overlain on the expanded copy of $A$, allowing us to construct
$P_{A}$ using vertices with integer coordinates. We now examine more carefully
how big this scaling factor should be, as a function of $\mu$, $\nu$, and
$\xi$, in order to construct $P_{A}$.

In order to achieve property P3, we set the width of each gadget in the scaled
grid to be $O(\xi\nu)$. To be able to maintain this width, over a gadget whose
length could be as much as $\mu$, we need the slopes of the tube edges to be
nearly parallel, but varying by each other by angles of magnitude
$\Theta(\xi\nu/\mu)$. And to be able to construct segments of these angles
using vertices of integer coordinates, to use as the tube edges of a gadget,
it suffices to choose the scaling factor of the grid to be $O(\xi^{2}\nu/\mu)$

We must also be able to construct the lenses of each gadget. It is possible to
form a convex chain of $a+b$ vertices within a square grid whose side length
is $\Theta((a+b)^{3/2})$ [26, 20]. Because our gadgets are very long and
narrow, the requirement that the two opposite lenses be completely visible to
each other does not significantly affect this bound. In order to fit a square
grid large enough to contain such a convex chain within the width of a single
gadget, it suffices to choose the scaling factor of the grid to be
$O((a+b)^{-3/2}\xi\nu)$.

Putting these two bounds for the scaling factor needed for the tubes and
lenses of our gadgets, we can perform our construction with a scaling factor
of

$\Theta\left(\max\left(\frac{\mu}{\xi^{2}\nu},\frac{(a+b)^{3/2}}{\xi\nu}\right)\right).$

Plugging in the values $\mu=O(|V(G)|^{4})$, $\nu=\Omega(1/|V(G)|^{4})$, and
$\xi=\Omega(1)$ coming from Section 3 gives us a scale factor of

$\Theta\left(\max\left(|V(G)|^{8},(a+b)^{3/2}|V(G)|^{4}\right)\right).$

When $a$ and $b$ are bounded by a polynomial of $|V(G)|$ (as they will be),
this allows our construction to be performed with integer coordinates of
polynomial magnitude.

###  4.2 Triangulation within a gadget

By looking at the way a triangulation of $P_{A}$ behaves within each gadget,
we can recover a non-crossing subset of segments of $A$ from the
triangulation, as the following definitions and lemmas show.

Figure 6: The local part of a triangulation in the gadget of a segment that is
active (top) or passive (bottom). A triangle of the top local part that
stretches from lens to lens, making the segment active, is highlighted by red
shading.

######  Definition .

For a triangulation $T$ of a polygon $P_{A}$, and a gadget $S$ of $P_{A}$
corresponding to a segment $s$ of $A$, we define the _local part_ of $T$ in
$S$ to be the set of triangles that have a side on one of the two lenses of
$S$. We say that segment $s$ of $A$ is _active_ in $T$ if its local part
includes at least one triangle that touches both lenses of $S$, and that $s$
is _passive_ otherwise.

See Figure 6 for an example, and note that (as in the figure) even when a
segment is passive, its triangulation may include triangles that block
visibility across the gadget.

######  Lemma .

The active segments of $A$ in any triangulation of $P_{A}$ form a non-crossing
set.

###### Proof.

If two segments cross, any lens-to-lens triangle within one segment crosses
any lens-to-lens triangle of the other. But in a triangulation, no two
triangles can cross each other. ∎

######  Lemma .

Let $T$ be a triangulation of $P_{A}$, let $s$ be an active segment of $A$ in
$T$, let $S$ be the corresponding gadget, bounded by polygon $\Pi_{S}$. Then
the intersection of $T$ and $\Pi_{S}$ is a triangulation of $\Pi_{S}$.

###### Proof.

By the construction of $P_{A}$, every edge of $T$ must belong to a single
gadget (as there are no other visibilities between pairs of vertices in
$P_{A}$). By the same argument as in subsection 4.2, no segment with its
endpoints in a single other gadget than $S$ can cross $\Pi_{S}$. Therefore,
all edges of $T$ that include an interior point of $\Pi_{S}$ must connect two
vertices of $S$, and lie within $\Pi_{S}$. It follows that all triangles of
$T$ that include an interior point of $\Pi_{S}$ must also lie within
$\Pi_{S}$. These triangles cover $\Pi_{S}$ and lie entirely within $\Pi_{S}$,
so they must form a triangulation of $\Pi_{S}$. ∎

######  Corollary .

Let $T$ be a triangulation of $P_{A}$, and let $L$ be a lens in polygonal
chain $C_{L}$ of a gadget $S$. Suppose that some active segment of $A$ in $T$
separates $C_{L}$ from the rest of $S$. Let $Q_{L}$ be the polygon formed from
$C_{L}$ by adding one more edge connecting the two endpoints of $C_{L}$. Then
$T$ intersects $Q_{L}$ in a triangulation of $Q_{L}$.

###### Proof.

By subsection 4.2, $T$ contains the edge connecting the endpoints of $C$. This
edge separates $Q_{L}$ from the rest of the polygon, so each triangle of $T$
must lie either entirely within or entirely outside $Q_{L}$. But the triangles
within $Q_{L}$ cover $Q_{L}$ (as the triangles of $T$ cover all of $P_{A}$) so
they form a triangulation of $Q_{L}$. ∎

These claims already allow us to produce a precise count of the triangulations
whose active segments form a maximum-size non-crossing subset, as a function
of the number of red segments in the subset, which we will do in the next
section. However, we also need to bound the number of triangulations with
smaller sets of active segments, and show that (with an appropriate choice of
the parameters $a$ and $b$) they form a negligible number of triangulations
compared to the ones coming from maximum-size non-crossing subsets.

###  4.3 Counting within a gadget

It is straightforward to count triangulations of the polygon formed by a
single lens:

Figure 7: Illustration for subsection 4.3: Closing off a lens $L$ by
connecting the endpoints of its path (red dashed edge $uv$) forms a polygon
$Q_{L}$ with as many distinct triangulations as lens vertices.

######  Lemma .

Let $Q_{L}$ be the polygon formed from a lens by closing its path off by a
single edge $uv$, as in subsection 4.2. Then the number of distinct
triangulations of $Q_{L}$ equals the number of vertices of the lens ($a$ for a
blue lens, $a+b$ for a red lens).

###### Proof.

Any triangulation of $Q_{L}$ is completely determined by the choice of apex of
the triangle that has $uv$ as one of its sides. All the remaining edges of the
triangulation must each connect one vertex of the lens to the remaining
visible endpoint of $uv$, the only vertex visible to that lens vertex (Figure
7). The number of choices for the apex equals the number of lens vertices. ∎

More generally, for any passive segment, we have:

######  Lemma .

Let $S$ be the gadget of segment $s$. Then the number of combinatorially
distinct ways to choose the local part in $S$ of a triangulation of $P_{A}$
for which $s$ is passive is polynomial in the number of lens vertices of $S$.

###### Proof.

Recall that the triangles of the local part each have one lens edge as one of
their sides. Within each lens, the only choice is where to place the apex of
each of these triangles. There are $O(1)$ choices of apex vertex, and within
each lens the edges whose triangles have a given apex must form a contiguous
subsequence. There are only polynomially many ways of partitioning the
sequences of lens edges into a constant number of contiguous subsequences. ∎

######  Lemma .

Let $T$ be a triangulation of $P_{A}$ and let $S$ be a gadget of $P_{A}$. Then
only $O(1)$ vertices of $S$ can participate in triangles of $T$ which are not
part of the local part of $T$ in $S$.

###### Proof.

$S$ has $O(1)$ vertices outside of its two lenses, so it has $O(1)$ non-lens
vertices that can participate in non-local triangles. A lens vertex can
participate in a non-local triangle in one of two ways: either the triangle
has one lens vertex and two non-lens vertices, or it has two vertices from
opposite lenses and one non-lens vertex. There are $O(1)$ edges of $T$ between
non-lens vertices of $S$, each of which is part of two triangles in $T$, so
there are $O(1)$ triangles in $S\cap T$ with only one lens vertex. Each non-
lens vertex of $S$ can participate in only one triangle whose other two
vertices are on opposite lenses, so again there are $O(1)$ triangles of this
type. Therefore, there are $O(1)$ lens vertices in non-local triangles. ∎

It is sufficiently messy to count the triangulations of active gadgets that we
provide here only approximate bounds. However, the exact number of
triangulations can be found in polynomial time using the algorithm for
counting triangulations of simple polygons [21, 35, 16].

Figure 8: Encoding a triangulation of the convex hull of two lenses by a
sequence of bits

######  Lemma .

Let $\Pi_{S}$ be the polygon bounding gadget $S$ (from subsection 4.1). Let
$\ell$ be the number of lens vertices of $\Pi_{S}$ ($2a$ for a blue gadget,
$2a+2b$ for a red gadget). Then the number of triangulations of $\Pi_{S}$ is
$\Theta(2^{\ell}/\sqrt{\ell})$.

###### Proof.

One can obtain $\Omega(2^{\ell}/\sqrt{\ell})$ triangulations by choosing a
maximal set of non-crossing lens-to-lens diagonals in $\Pi_{S}$, which form
the edges of a triangulation of the convex hull of the two lenses, and then
choosing arbitrarily a triangulation of the remaining polygons of $O(1)$
vertices on either side of the convex hull of the two lenses. The triangles
within any triangulation of the convex hull of the two lenses have a path as
their dual graph, and if they are ordered along the path then the
triangulation itself is determined by a sequence of bits (one bit per
triangle) that denote whether each triangle includes an edge of one lens or of
the other lens [24] (Figure 8). There are $\ell-2$ bits in the sequence,
exactly half of which must be zeros and half of which must be ones, so the
number of these triangulations is

$\binom{\ell-2}{(\ell-2)/2}=\Omega\left(\frac{2^{\ell}}{\sqrt{\ell}}\right).$

Figure 9: Encoding the local part of a triangulation by a sequence of bits

In the other direction, we can produce an overestimate of the number of
distinct local parts of triangulations of $\Pi_{S}$ by a similar method of
counting balanced binary strings of slightly greater length. As in Figure 8,
consider one of the two lenses as being “upper” (labeled by 1’s in the binary
string) and the other as being “lower” (labeled by 0’s). Similarly, we can
describe the two sides of the tube of the gadget as being left or right.
Suppose also that each side of a tube of the given gadget has $t$ internal
vertices (vertices that do not belong to either lens; for our gadgets,
$t\in\\{4,6\\}$). We describe the local part of a triangulation by a sequence
of bits, as follows (Figure 9):

  * •

$t$ blocks of 0-bits, each terminated by a single 1-bit, specifying how many
edges of the lower lens form triangles whose apex is at each of the internal
vertices of the left side of the tube.

  * •

$t$ blocks of 1-bits, each terminated by a single 0-bit, specifying how many
edges of the upper lens form triangles whose apex is at each of the internal
vertices of the left side of the tube.

  * •

A sequence of bits as before describing the left-to-right sequence of
triangles that have all three vertices on the two lenses, with a 0-bit for a
triangle with a side on the lower lens and a 1-bit for a triangle with a side
on the upper lens.

  * •

$t$ blocks of 0-bits, each terminated by a single 1-bit, specifying how many
edges of the lower lens form triangles whose apex is at each of the internal
vertices of the right side of the tube.

  * •

$t$ blocks of 1-bits, each terminated by a single 0-bit, specifying how many
edges of the upper lens form triangles whose apex is at each of the internal
vertices of the right side of the tube.

The resulting sequence of bits uniquely describes each distinct local part,
has $2\ell-2+4t$ bits, and has equal numbers of 0- and 1-bits. Not all such
sequences of bits describe a valid local part (they may specify triangles
connecting the lower and upper lenses to the tubes that cross each other) but
this is non-problematic. There are $O(2^{\ell}/\sqrt{\ell})$ possible
sequences of bits of this type, so there are $O(2^{\ell}/\sqrt{\ell})$ local
parts of triangulations of $\Pi_{S}$. Each local part leaves remaining
untriangulated regions on the left and right sides of $\Pi_{S}$ with $O(1)$
vertices (as in the proof of subsection 4.3) so it can be extended to a
complete triangulation in $O(1)$ distinct ways. Therefore, the total number of
triangulations of $\Pi_{S}$ is $O(2^{\ell}/\sqrt{\ell})$. ∎

###  4.4 Global counting

The key properties of the number of triangulations of $P_{A}$ (with an
appropriate choice of $a$ and $b$) that allow us to prove our counting
reduction are that

  * •

the number of triangulations coming from any particular maximum-size non-
crossing subset of $A$ can be determined only from the size of the arrangement
and the number of red segments in the subset, and

  * •

non-crossing subsets that use fewer segments than the maximum, or that use the
maximum total number of segments but fewer than the maximum possible number of
red segments, contribute a negligible fraction of the total number of
triangulations.

In this section we make these notions precise.

Figure 10: The twelve-sided polygon in the center of two crossing red gadgets

######  Definition .

We define the following numerical parameters:

  * •

$\alpha$ is the number of triangulations of polygon $\Pi_{S}$ (as defined in
subsection 4.1) for a blue gadget $S$, counting only the triangulations in
which at least one triangle has three lens vertices. The definition of the
gadgets causes gadgets of the same color to have equal numbers of
triangulations.

  * •

$\beta$ is the number of triangulations of $\Pi_{S}$ for a red gadget $S$,
again counting only the triangulations in which at least one triangle has
three lens vertices.

  * •

$\gamma$ is the number of triangulations of the twelve-sided polygon formed in
the center of two crossing red gadgets by the four shared vertices of the two
gadgets and their four neighbors in each gadget (Figure 10). The constraints
on how gadgets can cross imply that this number is independent of the choice
of which two gadgets cross.

  * •

$q_{n,r}$, for any $n\geq 0$ and $0\leq r\leq n/2$, is
$\alpha^{n-r}\beta^{r}\gamma^{(n-2r)/2}a^{2r}(a+b)^{2(n-r)}2^{3r}$.

The requirement in the definition of $\alpha$ and $\beta$ that the
triangulations have a triangle with three lens vertices implies that these
triangulations are exactly the ones that can appear in triangulations of
$P_{A}$ for which the corresponding segment of $A$ is active. We do not derive
an explicit formula for $\alpha$ and $\beta$, although they are bounded to
within a constant factor by subsection 4.3. Therefore, it is important for us
that they can be calculated in polynomial time by dynamic programming, as (for
appropriate choices of $a$ and $b$) they count triangulations of simple
polygons of polynomial size. (The constraint on the existence of a triangle
with three lens vertices is not problematic for this dynamic programming
algorithm.)

Figure 11: A maximum-non-crossing subset of a red–blue arrangement (consisting
of four blue segments and no red segments), and the associated partition of
$P_{A}$ into smaller polygons (shown by the black segments). These smaller
polygons include a polygon $\Pi_{S}$ for the gadget $S$ of each active segment
$s$, two polygons $Q_{L}$ for the lenses of each gadget of a passive segment,
and a twelve-sided polygon for each crossing of two passive red gadgets. Not
shown: the central quadrilaterals of passive blue gadgets and of passive red
gadgets crossed by an active red gadget.

######  Lemma .

Let $A$ be a red–blue arrangement with $n$ red and $n$ blue segments. Let
$\Xi$ be a maximum-size non-crossing subset of $A$, with $r=r(\Xi)$ red
segments. Then the number of triangulations of $P_{A}$ in which $\Xi$ forms
the active set is $q_{n,r}$.

###### Proof.

By subsection 4.2, the triangulations with $\Xi$ active can be partitioned
into the polygons $\Pi_{S}$ for the active segments of $\Xi$ and the remaining
smaller polygons left by the removal of these polygons, each of which can be
triangulated independently and each of which contributes a factor to the
product in the definition of $q_{n,r}$. Figure 11 illustrates this partition
into polygons. There are $r$ active red segments and $n-r$ active blue
segments, each of which contributes a polygon $\Pi_{S}$ to the partition and a
factor of $\beta$ or $\alpha$ (respectively) to the product by which $q_{n,r}$
was defined. There are $2r$ lenses of passive blue segments and $2(n-r)$
lenses of passive red segments, each of which contributes a polygon $Q_{L}$
containing the lens and a factor of $a$ or $(a+b)$ to the product,
respectively, by subsection 4.2 and subsection 4.3.

The $r$ active red segments and $r$ passive red segments that they cross leave
$n-2r$ red segments that are passive but not crossed by another active red
segment. These $n-2r$ red segments form $(n-2r)/2$ twelve-sided polygons where
their gadgets cross each other in pairs, with each pair contributing a factor
of $\gamma$ to the product.

The remaining factor of $2^{3r}$ in the product comes from the $r$ passive
blue gadgets, each of which has a central quadrilateral between the two red
active segments that cross it, and from the $r$ passive red gadgets that are
crossed by an active red gadget, each of which has two central quadrilaterals
between the consecutive pairs of the three active segments that cross it.
These $3r$ quadrilaterals each can be triangulated in two ways. ∎

######  Corollary .

Suppose that $a\geq b$. Then $q_{n,r}/q_{n,r-1}=\Theta(2^{2b})$.

###### Proof.

Expanding the definition of $q_{n,r}$ and eliminating common factors with
$q_{n,r-1}$ produces

$\frac{q_{n,r}}{q_{n,r-1}}=\frac{8\beta
a^{2}}{\alpha\gamma(a+b)^{2}}=\Theta\Bigl{(}\frac{\beta}{\alpha}\Bigr{)}.$

Here, $\gamma$ has been eliminated from the right hand side as a constant, and
the assumption that $a\geq b$ implies that $1/4\leq a^{2}/(a+b)^{2}\leq 1$
allowing the elimination of those factors as well. Applying subsection 4.3 to
bound both $\alpha$ and $\beta$ to within constants gives
$\beta/\alpha=\Theta(2^{2b})$, the stated bound. ∎

######  Lemma .

Suppose the parameters $a$ and $b$ are both upper-bounded by polynomials of
$n$. Then

$\log_{2}q_{n,r}=2an+2rb\pm O(n\log n),$

where the constant in the $O$-notation depends on the bounds on $a$ and $b$.

###### Proof.

In the formula for $q_{n,r}$, each factor of $\alpha$ contributes $2a-O(\log
n)$ to the logarithm, each factor of $\beta$ contributes $2a+2b-O(\log n)$,
each factor of $a$ or $b$ contributes $O(\log n)$, and each factor of $\gamma$
or $2$ contributes $O(1)$. The result follows by adding these contributions
according to their exponents. ∎

######  Lemma .

Suppose the parameters $a$ and $b$ are both upper-bounded by polynomials of
$n$. Let $p$ denote the number of triangulations of $P_{A}$ that do not have a
maximum-size non-crossing subset of $A$ as their active set. Then

$\log_{2}p\leq 2a(n-1)+2b(n-1)+O(n\log n).$

###### Proof.

We bound $p$ by a product of the number of active sets, the numbers of local
parts of triangulations for each gadget, and the numbers of ways of extending
a choice of local parts to a full triangulation. This corresponds to bounding
$\log_{2}p$ by a sum of terms, one for each of these factors.

There are $2n$ segments of $A$, so at most $2^{2n}$ subsets of these segments
that can be chosen as the active set, contributing a term of at most $2n$ to
the logarithm. By subsection 4.2, the active set can be only a maximum-size
non-crossing subset or a non-crossing subset of smaller than the maximum size
$n$, and this lemma considers only the case where it is of smaller than
maximum size, so each non-maximum active set can have at most $n-1$ active
segments. By subsection 4.3, the number of choices of local parts of gadgets
for active segments adds at most $2a(n-1)+2b(n-1)-O(n\log n)$ to the
logarithm. The local parts of the gadgets for passive segments can be chosen
in a number of ways per gadget that is polynomial in $a$ and $b$ by subsection
4.3, adding another $O(n\log n)$ term to the logarithm. Once the active
gadgets have been triangulated and the local parts of the passive gadgets have
been chosen, the regions that remain to be triangulated have a total of $O(n)$
vertices by subsection 4.3, so the number of ways to triangulate them
contributes another $O(n)$ to the logarithm. ∎

###  4.5 Completing the reduction

We have already described how to transform an arrangement $A$ into a polygon
$P_{A}$, modulo the choice of the parameters $a$ and $b$. To complete the
description of our reduction, we need to set $a$ and $b$ and we need to
describe how to recover the number of maximum-size non-crossing subsets of $A$
from the number $N$ of triangulations of $P_{A}$.

Given a red–blue arrangement $A$ with $n$ red and $n$ blue segments, set
$b=2n$. By subsection 4.4, with this choice, $q_{n,r-1}$ and $q_{n,r}$ differ
by a factor of $\Theta(2^{4n})$, much larger than the $2^{2n}$ bound on the
total number of non-crossing sets of segments. Therefore, for all sufficiently
large $n$ and all $r\leq n$, the number of triangulations with a maximum-size
non-crossing set of active segments that includes fewer than $r$ red segments
is strictly less than $q_{n,r}$. Next, set $a=3n^{2}$. This is large enough
that, for sufficiently large $n$, the number $p$ of triangulations whose
active set is non-maximum is strictly smaller than $q_{n,0}$. This follows
because the bound of subsection 4.4 on $q_{n,0}$ has a larger multiple of $a$
than does the bound of subsection 4.4 on $p$, and the $O(n\log n)$ term and
larger multiple of $b$ in subsection 4.4 are not large enough to make up for
this difference.

With these choices of $a$ and $b$, we also have that $q_{n-1,n-1}$ is smaller
than $q_{n,0}$ by a factor of $2^{\Omega(n^{2})}$. Thus, for all sufficiently
large $n$, if $A^{\prime}$ is any red–blue arrangement with fewer than $n$ red
and blue segments, the total number of triangulations of $P_{A^{\prime}}$ is
strictly smaller than $q_{n,0}$. This implies that, from the total number $N$
of triangulations of $P_{A}$ we can unambiguously determine the number of
segments in $A$.

With these considerations, we are ready to prove the correctness of our
reduction:

###### Proof of Theorem 1.

Counting triangulations of a given polygon $P$ is in $\\#\mathsf{P}$ by
subsection 2.2, so we can complete the proof by describing a polynomial-time
counting reduction from the number of maximum-size non-crossing subsets of a
red–blue arrangement $A$ (proved $\\#\mathsf{P}$-hard in Section 3). To
transform $A$ into a polygon, let $n$ be the number of red segments in $A$.
Our reduction will work for all sufficiently large $n$, larger than some fixed
threshold $n^{\prime}$; the reduction algorithm compares $n$ to this threshold
and, for $n<n^{\prime}$, directly computes the number of maximum-size non-
crossing subsets of $A$ (by a brute force search over all subsets, in time
$O(2^{n^{\prime}}(n^{\prime})^{O(1)})=O(1)$) and constructs a polygon with the
same number of triangulations using the formula for numbers of triangulations
of lens polygons of subsection 4.3. Otherwise, it chooses $a=3n^{2}$ and
$b=2n$ as above, and constructs the polygon $P_{A}$.

To transform the number $N$ of triangulations of the given polygon into the
number of maximum-size non-crossing subsets of $A$, first check whether this
number is sufficiently small that it comes from our special-case construction
for bounded values of $n$. If so, directly decode it to the number of maximum-
size non-crossing subsets.

In the remaining case, recover $n$ as the unique value that could have
produced a polygon $P_{A}$ with $N$ triangulations. From $n$, compute the
associated parameters $a$ and $b$, use the dynamic programming algorithm for
counting triangulations of simple polygons to compute the parameters $\alpha$
and $\beta$, and use these values to compute the parameters $q_{n,i}$. For
each choice of $r$ from $n$ down to $0$ (in decreasing order) compute the
number of maximum-size non-crossing subsets with $r$ red segments as $\lfloor
N^{\prime}/q_{n,r}\rfloor$ (where $N^{\prime}$ starts with the value $N$ and
is reduced as the algorithm progresses) and then replace $N^{\prime}$ by
$N^{\prime}$ mod $q_{n,r}$ before proceeding to the next value of $r$. Sum the
numbers of maximum-non-crossing subsets obtained for each value of $r$ to
obtain the total number of maximum-size non-crossing subsets.

When computing the number of non-crossing subsets for each value of $r$, the
contributions from triangulations whose active segments include more red
segments than $r$ will already have been subtracted off, by induction. The
contributions from triangulations whose active segments include fewer red
segments than $r$, or from triangulations that do not have maximum-size non-
crossing sets of active segments, will sum to less than a single multiple of
the number of triangulations for each non-crossing set with the given number
of red segments, as discussed above. Therefore, each number of non-crossing
subsets is computed correctly. ∎

##  5 Conclusions and open problems

We have shown that counting triangulations of polygons with holes is
$\\#\mathsf{P}$-complete under Turing reductions. It would be of interest to
tighten this result to show completeness under counting reductions, or even
under parsimonious reductions. Can this be done, either by strengthening the
type of reduction used for the underlying graph problem that we reduce from,
independent sets in regular planar graphs, or by finding a different reduction
for triangulations that bypasses the Turing reductions used for this graph
problem?

In a triangulation of a polygon with holes, every hole has a diagonal
connecting its leftmost vertex to a vertex to the left of it in another
boundary component. By testing all combinations of these left diagonals, and
using dynamic programming to count triangulations of the simple polygon formed
by cutting the input along one of these sets of diagonals (avoiding
triangulations that use previously-tested diagonals) it is possible to count
triangulations of an $n$-vertex polygon with $h$ holes in time $O(n^{h+3})$.
Is the dependence on $h$ in the exponent of $n$ necessary, or is there a
fixed-parameter tractable algorithm for this problem?

More generally, there are many other counting problems in discrete geometry
for which we neither know a polynomial time algorithm nor a hardness proof.
For instance, we do not know the complexity of counting triangulations, planar
graphs, non-crossing Hamiltonian cycles, non-crossing spanning trees, or non-
crossing matchings of sets of $n$ points in the plane. Are these problems
hard?

## Acknowledgements

A preliminary version of this paper appeared in the Proceedings of the 2019
International Symposium on Computational Geometry. This work was supported in
part by the US National Science Foundation under grants CCF-1618301 and
CCF-1616248.

## References

  * [1] Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber, _An improved lower bound on the minimum number of triangulations_ , Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016) (Dagstuhl, Germany) (Sándor Fekete and Anna Lubiw, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016, pp. A7:1–A7:16, doi:10.4230/LIPIcs.SoCG.2016.7, MR 3540850.
  * [2] Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber, _On the number of plane geometric graphs_ , Graphs and Combinatorics 23 (2007), no. suppl. 1, 67–84, doi:10.1007/s00373-007-0704-5, MR 2320619.
  * [3] Oswin Aichholzer, Ferran Hurtado, and Marc Noy, _A lower bound on the number of triangulations of planar point sets_ , Comput. Geom. Theory and Applications 29 (2004), no. 2, 135–145, doi:10.1016/j.comgeo.2004.02.003, MR 2082211.
  * [4] Oswin Aichholzer, David Orden, Francisco Santos, and Bettina Speckmann, _On the number of pseudo-triangulations of certain point sets_ , J. Combin. Theory Ser. A 115 (2008), no. 2, 254–278, doi:10.1016/j.jcta.2007.06.002, MR 2382515.
  * [5] Victor Alvarez, Karl Bringmann, Radu Curticapean, and Saurabh Ray, _Counting triangulations and other crossing-free structures via onion layers_ , Discrete Comput. Geom. 53 (2015), no. 4, 675–690, doi:10.1007/s00454-015-9672-3, MR 3341573.
  * [6] Victor Alvarez, Karl Bringmann, Saurabh Ray, and Raimund Seidel, _Counting triangulations and other crossing-free structures approximately_ , Comput. Geom. Theory and Applications 48 (2015), no. 5, 386–397, doi:10.1016/j.comgeo.2014.12.006, MR 3319102.
  * [7] Victor Alvarez and Raimund Seidel, _A simple aggregative algorithm for counting triangulations of planar point sets and related problems_ , Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG’13) (New York) (Timothy Chan and Rolf Klein, eds.), ACM, 2013, pp. 1–8, doi:10.1145/2462356.2462392, MR 3208190.
  * [8] Emile E. Anclin, _An upper bound for the number of planar lattice triangulations_ , J. Combin. Theory Ser. A 103 (2003), no. 2, 383–386, doi:10.1016/S0097-3165(03)00097-9, MR 1996075.
  * [9] Takao Asano, Tetsuo Asano, and Hiroshi Imai, _Partitioning a polygonal region into trapezoids_ , J. ACM 33 (1986), no. 2, 290–312, doi:10.1145/5383.5387, MR 835106.
  * [10] Andrei Asinowski and Günter Rote, _Point sets with many non-crossing perfect matchings_ , Comput. Geom. Theory and Applications 68 (2018), 7–33, doi:10.1016/j.comgeo.2017.05.006, MR 3715040.
  * [11] Marshall W. Bern and David Eppstein, _Mesh generation and optimal triangulation_ , Computing in Euclidean Geometry (Ding-Zhu Du and Frank K. Hwang, eds.), Lecture Notes Series on Computing, vol. 4, World Scientific, 2nd ed., 1995, pp. 47–123.
  * [12] Sergei Bespamyatnikh, _An efficient algorithm for enumeration of triangulations_ , Comput. Geom. Theory and Applications 23 (2002), no. 3, 271–279, doi:10.1016/S0925-7721(02)00111-6, MR 1927136.
  * [13] Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, and Jack Snoeyink, _Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm_ , SIAM J. Comput. 36 (2006), no. 3, 721–739, doi:10.1137/050631008, MR 2263009.
  * [14] Jérémie Chalopin and Daniel Gonçalves, _Every planar graph is the intersection graph of segments in the plane: extended abstract_ , Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 (Michael Mitzenmacher, ed.), 2009, pp. 631–638, doi:10.1145/1536414.1536500.
  * [15] Hubert de Fraysseix, János Pach, and Richard Pollack, _How to draw a planar graph on a grid_ , Combinatorica 10 (1990), 41–51, doi:10.1007/BF02122694, MR 1075065.
  * [16] Q. Ding, J. Qian, W. Tsang, and C. Wang, _Randomly generating triangulations of a simple polygon_ , Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China, August 16–19, 2005, Proceedings (Lusheng Wang, ed.), Lecture Notes in Computer Science, vol. 3595, Springer, Berlin, 2005, pp. 471–480, doi:10.1007/11533719_48, MR 2190870.
  * [17] Samuel Dittmer and Igor Pak, _Counting linear extensions of restricted posets_ , Electronic preprint arxiv:1802.06312, 2018.
  * [18] Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth, _Bounds on the maximum multiplicity of some common geometric graphs_ , SIAM J. Discrete Math. 27 (2013), no. 2, 802–826, doi:10.1137/110849407, MR 3044105.
  * [19] Martin Dyer, Leslie Ann Goldberg, and Mike Paterson, _On counting homomorphisms to directed acyclic graphs_ , J. ACM 54 (2007), no. 6, A27:1–A27:23, doi:10.1145/1314690.1314691, MR 2374028.
  * [20] David Eppstein, _Forbidden Configurations in Discrete Geometry_ , Cambridge University Press, 2018, Section 11.2, pp. 110–113.
  * [21] Peter Epstein and Jörg-Rüdiger Sack, _Generating triangulations at random_ , ACM Trans. Model. Comput. Simul. 4 (1994), no. 3, 267–278, doi:10.1145/189443.189446.
  * [22] Philippe Flajolet and Marc Noy, _Analytic combinatorics of non-crossing configurations_ , Discrete Math. 204 (1999), no. 1-3, 203–229, doi:10.1016/S0012-365X(98)00372-0, MR 1691870.
  * [23] Alfredo García, Marc Noy, and Javier Tejel, _Lower bounds on the number of crossing-free subgraphs of $K_{N}$_, Comput. Geom. Theory and Applications 16 (2000), no. 4, 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294.
  * [24] Ferran Hurtado, Marc Noy, and Jorge Urrutia, _Flipping edges in triangulations_ , Discrete Comput. Geom. 22 (1999), no. 3, 333–346, doi:10.1007/PL00009464, MR 1706610.
  * [25] F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, _On the computational complexity of the Jones and Tutte polynomials_ , Math. Proc. Cambridge Philos. Soc. 108 (1990), no. 1, 35–53, doi:10.1017/S0305004100068936, MR 1049758.
  * [26] Vojtěch Jarník, _Über die Gitterpunkte auf konvexen Kurven_ , Math. Z. 24 (1926), no. 1, 500–518, doi:10.1007/BF01216795, MR 1544776.
  * [27] Volker Kaibel and Günter M. Ziegler, _Counting lattice triangulations_ , Surveys in Combinatorics 2003: Papers from the 19th British Combinatorial Conference held at the University of Wales, Bangor, June 29–July 4, 2003 (C. D. Wensley, ed.), London Math. Soc. Lecture Note Ser., vol. 307, Cambridge Univ. Press, Cambridge, UK, 2003, pp. 277–307, arXiv:math/0211268, MR 2011739.
  * [28] Pegah Kamousi and Subhash Suri, _Stochastic minimum spanning trees and related problems_ , Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2011, San Francisco, California, USA, January 22, 2011 (Philippe Flajolet and Daniel Panario, eds.), SIAM, 2011, pp. 107–116, doi:10.1137/1.9781611973013.12, MR 2815489.
  * [29] Goos Kant and Hans L. Bodlaender, _Triangulating planar graphs while minimizing the maximum degree_ , Inform. and Comput. 135 (1997), no. 1, 1–14, doi:10.1006/inco.1997.2635, MR 1451493.
  * [30] Marek Karpinski, Andrzej Lingas, and Dzmitry Sledneu, _A QPTAS for the base of the number of crossing-free structures on a planar point set_ , Theoretical Computer Science 711 (2018), 56–65, doi:10.1016/j.tcs.2017.11.003, MR 3778824.
  * [31] Nathan Linial, _Hard enumeration problems in geometry and combinatorics_ , SIAM J. Algebraic Discrete Methods 7 (1986), no. 2, 331–335, doi:10.1137/0607036, MR 830652.
  * [32] Anna Lubiw, _Decomposing polygonal regions into convex quadrilaterals_ , Proceedings of the 1st Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985 (New York) (Joseph O’Rourke, ed.), ACM, 1985, pp. 97–106, doi:10.1145/323233.323247.
  * [33] Dániel Marx and Tillmann Miltzow, _Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems_ , Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016) (Dagstuhl, Germany) (Sándor Fekete and Anna Lubiw, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016, pp. A52:1–A52:16, doi:10.4230/LIPIcs.SoCG.2016.52, MR 3540894.
  * [34] Alexander Pilz and Carlos Seara, _Convex quadrangulations of bichromatic point sets_ , Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), 2017, available from https://mat-web.upc.edu/people/carlos.seara/data/publications/internationalConferences/EuroCG-17_paper_23.pdf.
  * [35] Saurabh Ray and Raimund Seidel, _A simple and less slow method for counting triangulations and for related problems_ , Proceedings of the 20th European Workshop on Computational Geometry (EuroCG 2004), 2004, available from https://hdl.handle.net/11441/55368.
  * [36] Francisco Santos and Raimund Seidel, _A better upper bound on the number of triangulations of a planar point set_ , J. Combin. Theory Ser. A 102 (2003), no. 1, 186–193, doi:10.1016/S0097-3165(03)00002-5, MR 1970985.
  * [37] Edward R. Scheinerman, _Intersection Classes and Multiple Intersection Parameters of Graphs_ , Ph.D. thesis, Princeton University, 1984.
  * [38] Walter Schnyder, _Embedding planar graphs on the grid_ , Proceedings of the First Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 1990, 22-24 January 1990, San Francisco, California, USA (David S. Johnson, ed.), 1990, pp. 138–148, available from https://dl.acm.org/citation.cfm?id=320176.320191.
  * [39] Raimund Seidel, _On the number of triangulations of planar point sets_ , Combinatorica 18 (1998), no. 2, 297–299, doi:10.1007/PL00009823, MR 1656547.
  * [40] Micha Sharir and Adam Sheffer, _Counting triangulations of planar point sets_ , Electron. J. Combin. 18 (2011), no. 1, P70:1–P70:74, available from https://emis.ams.org/journals/EJC/Volume_18/PDF/v18i1p70.pdf, MR 2788687.
  * [41] Micha Sharir, Adam Sheffer, and Emo Welzl, _Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique_ , J. Combin. Theory Ser. A 120 (2013), no. 4, 777–794, doi:10.1016/j.jcta.2013.01.002, MR 3022612.
  * [42] Micha Sharir and Emo Welzl, _On the number of crossing-free matchings, cycles, and partitions_ , SIAM J. Comput. 36 (2006), no. 3, 695–720, doi:10.1137/050636036, MR 2263008.
  * [43] Salil P. Vadhan, _The complexity of counting in sparse, regular, and planar graphs_ , SIAM J. Comput. 31 (2001), no. 2, 398–427, doi:10.1137/S0097539797321602, MR 1861282.
  * [44] L. G. Valiant, _The complexity of computing the permanent_ , Theoretical Computer Science 8 (1979), no. 2, 189–201, doi:10.1016/0304-3975(79)90044-6, MR 526203.
  * [45] Manuel Wettstein, _Counting and enumerating crossing-free geometric graphs_ , J. Comput. Geom. 8 (2017), no. 1, 47–77, doi:10.20382/jocg.v8i1a4, MR 3649672.
  * [46] Mingji Xia, Peng Zhang, and Wenbo Zhao, _Computational complexity of counting problems on 3-regular planar graphs_ , Theoretical Computer Science 384 (2007), no. 1, 111–125, doi:10.1016/j.tcs.2007.05.023, MR 2354227.