  Given a set of $n$ points on a plane, in the Minimum Weight Triangulation
problem, we wish to find a triangulation that minimizes the sum of Euclidean
length of its edges. This incredibly challenging problem has been studied for
more than four decades and has been only recently shown to be NP-Hard. In this
paper we present a novel polynomial-time algorithm that computes a
$14$-approximation of the minimum weight triangulation -- a constant that is
significantly smaller than what has been previously known.
  In our algorithm, we use grids to partition the edges into levels where
shorter edges appear at smaller levels and edges with similar lengths appear at
the same level. We then triangulate the point set incrementally by introducing
edges in increasing order of their levels. We introduce the edges of any level
$i+1$ in two steps. In the first step, we add edges using a variant of the
well-known ring heuristic to generate a partial triangulation
$\hat{\mathcal{A}}_i$. In the second step, we greedily add non-intersecting
level $i+1$ edges to $\hat{\mathcal{A}}_i$ in increasing order of their length
and obtain a partial triangulation $\mathcal{A}_{ i+1}$. The ring heuristic is
known to yield only an $O(\log n)$-approximation even for a convex polygon and
the greedy heuristic achieves only a $\Theta(\sqrt{n})$-approximation.
Therefore, it is surprising that their combination leads to an improved
approximation ratio of $14$.
  For the proof, we identify several useful properties of $\hat{\mathcal{A}}_i$
and combine it with a new Euler characteristic based technique to show that
$\hat{\mathcal{A}}_i$ has more edges than $\mathcal{T}_i$; here $\mathcal{T}_i$
is the partial triangulation consisting of level $\le i$ edges of some minimum
weight triangulation. We then use a simple greedy stays ahead proof strategy to
bound the approximation ratio.
