Optimal gridpositioning or single facility location on the torus

A finite set of points in the plane must be approximated by gridpoints of an orthogonal grid of fixed orientation and mesh. The problem is to find the position of the grid which minimises the total approximation error. The paper shows how this problem may be viewed as a single facility location problem on the two-dimensional torus, which can be solved by an adapted big square small square method for general errormeasures. Two particular errormeasures-the sum of rectilinear errorlengths and the sum of squared euclidean errorlengths-give rise to very efficient solution methods. In these cases the problem can be decomposed into two independent location problems on a circular network, solvable in linear time after sorting.