Minimum-weight triangulation is NP-hard

In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set $S$ in the Euclidean plane and two triangulations $T_1$ and ...

Let $\Poly$ be a simple polygon with $n$ vertices. The \emph{dual graph} $\triang^*$ of a triangulation~$\triang$ of~$\Poly$ is the graph whose vertices correspond to the bounded faces of $\triang$ and whose edges connect those faces of~$\triang$ that share an edge. We consider triangulations of~$\Poly$ that minimize or maximize the diameter of their dual graph. We show that both triangulations can be constructed in $O(n^3\log n)$ time using dynamic programming. If $\Poly$ is...

The number of triangulations of a planar n point set is known to be $c^n$, where the base $c$ lies between $2.43$ and $30.$ The fastest known algorithm for counting triangulations of a planar n point set runs in $O^*(2^n)$ time. The fastest known arbitrarily close approximation algorithm for the base of the number of triangulations of a planar n point set runs in time subexponential in $n.$ We present the first quasi-polynomial approximation scheme for the base of the number ...

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, we derive new...

A $3$-matching of a graph is a partition of its vertices into $3$-element subsets; this generalizes the idea of matchings in graphs. Let $G$ be a complete edge-weighted graph; to each $3$-set of vertices of $G$ assign the sum of its minimum spanning tree as its weight. The $3$-Matching Problem is the combinatorial optimization problem of finding a minimum weight $3$-matching of $G$, where the weight of a $3$-matching is the sum of the weights of its $3$-sets. While the $3$-Ma...

Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph G are triangular line graphs, which have been studied under many names including anti-Gallai graphs, 2-in-3 graphs, and link graphs. While closely related to line graphs, triangular line graphs have been di...

Given a set P of points in the plane, an Euclidean t-spanner for P is a geometric graph that preserves the Euclidean distances between every pair of points in P up to a constant factor t. The weight of a geometric graph refers to the total length of its edges. In this paper we show that the problem of deciding whether there exists an Euclidean t-spanner, for a given set of points in the plane, of weight at most w is NP-hard for every real constant t > 1, both whether planarit...

The geometric $\delta$-minimum spanning tree problem ($\delta$-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $\delta$, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $\delta$-minimum bottleneck spanning tree problem ($\delta$-MBST), is the problem of finding a degree bounded spanning tree such that the length of the...

The problem of finding a triangulation of a convex three-dimensional polytope with few tetrahedra is proved to be NP-hard. We discuss other related complexity results.

We prove the #P-hardness of the counting problems associated with various satisfiability, graph and combinatorial problems, when restricted to planar instances. These problems include \begin{romannum} \item[{}] {\sc 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover.} \end{romannum} We also prove the {\sf NP}-completeness of the {\sc Ambiguous Satisfiability} problems \cite{Sa80} a...