  The {\it matrix-chain multiplication} problem is a classic problem that is
widely taught to illustrate dynamic programming. The textbook solution runs in
$\theta(n^3)$ time. However, there is a complex $O(n \log n)$-time method
\cite{HU82}, based on triangulating convex polygons, and a description without
proofs or implementation detail, of a much simpler $O(n^2)$-time method
\cite{YAO82}. There is also a linear-time approximation algorithm with a small
worst-case error bound \cite{HU-SHING1981}. In this paper, we make five
contributions both to theory and pedagogy: 1) We simplify the approach in
\cite{YAO82}, and provide complete, correct proofs and implementation details,
to establish the $O(n^2)$-time bound. We believe that this exposition is simple
enough for classroom use. 2) We extend the $O(n^2)$-time bound to a natural
class of polygon-triangulation problems that generalizes the original
polygon-triangulation problem in \cite{HU82}. 3) We show that the worst-case
running time of the method in \cite{YAO82}, and of our version, is
$\Theta(n^2)$. 4) We show that in a natural variant of the original
polygon-triangulation problem, the approximation method of \cite{HU-SHING1981}
does not achieve the same error bound, but does achieve an error bound about
twice the original bound. 5) We detail empirical testing, showing that on
random data our variant runs in $\Theta(n \log n)$ time, while the approach in
\cite{YAO82} empirically takes $\Theta(n^2)$ time. Software for these tests is
posted on the web.
