×

Optimal gridpositioning or single facility location on the torus. (English) Zbl 0732.90057

Summary: 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 minimizes the total approximation error. We show 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 error measures. Two particular error measures - the sum of rectilinear error lengths and the sum of squared euclidean error lengths - 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.

MSC:

90B85 Continuous location
PDFBibTeX XMLCite
Full Text: DOI EuDML