A storage-efficient method for construction of a Thiessen triangulation (Q1060525)

The paper addresses the problem of triangulating a set of two-dimensional data points. Among the many possible triangulations, the one arising from the Thiessen (or Voroni or Dirichlet) tesselation of the data points has several desirable properties. The described method does not construct the Thiessen tesselation but builds the triangulation by optimizing an initial triangulation (swapping of diagonals). A presorting of the data points is carried out which, in connection with the described data structure, proves to be time efficient. The algorithm and the used data structure are then compared to other methods.