Abstract: Anisotropic centroidal Voronoi tessellations (CVT) are a useful tool for segmenting surfaces in geometric modeling. We present a new approach to anisotropic CVT, where the local distance metric is learned from the embedding of the shape. Concretely, we define the distance metric implicitly as the minimizer of the CVT energy. Constraining the metric tensors to have unit determinant leads to the optimal distance metric being the inverse covariance matrix of the data (i.e. Mahalanobis distances). We explicitly cover the case of degenerate covariance and provide an algorithm to minimize the CVT energy. The resulting technique has applications in shape approximation, particularly in the case of noisy data, where normals are unreliable. We also put our approach in the context of other techniques. Among others, we show that Variational Shape Approximation can be interpreted in the same framework by constraining the metric tensor based on another norm.