  The construction of anisotropic triangulations is desirable for various
applications, such as the numerical solving of partial differential equations
and the representation of surfaces in graphics. To solve this notoriously
difficult problem in a practical way, we introduce the discrete Riemannian
Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi
diagram. This structure has been implemented and was shown to lead to good
triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as
detailed in our experimental companion paper.
  In this paper, we study theoretical aspects of our structure. Given a finite
set of points $\cal P$ in a domain $\Omega$ equipped with a Riemannian metric,
we compare the discrete Riemannian Voronoi diagram of $\cal P$ to its
Riemannian Voronoi diagram. Both diagrams have dual structures called the
discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide
conditions that guarantee that these dual structures are identical. It then
follows from previous results that the discrete Riemannian Delaunay complex can
be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic
triangulation with curved simplices. Furthermore, we show that, under similar
conditions, the simplices of this triangulation can be straightened.
