  We study the problem of finding a triangulation T of a planar point set S
such as to minimize the expected distance between two points x and y chosen
uniformly at random from S. By distance we mean the length of the shortest path
between x and y along edges of T. The length of a path is the sum of the
weights of its edges. Edge weights are assumed to be given as part of the
problem for every pair of distinct points (x,y) in S^2.
  In a different variant of the problem, the points are vertices of a simple
polygon and we look for a triangulation of the interior of the polygon that is
optimal in the same sense.
  We prove that a general formulation of the problem in which the weights are
arbitrary positive numbers is strongly NP-complete. For the case when all the
weights are equal we give polynomial-time algorithms. In the end we mention
several open problems.
