An Algorithm for Best Approximation of a Line by Lattice Points in Three Dimensions
Vaughan L. Clarkson, Jane Perkins, Iven Mareels · 1995
In this paper we present an algorithm for finding successive best approximations of a line by lattice points in three dimensions. Our algorithm is primarily an extension of the work of Furtwangler [13], which has been generalised for arbitrary radius functions, lattices and initial bases. We show that, after a finite number of initialisation iterations, the algorithm will produce all best approximations to the line above a certain height. Conversely, we show that, after initialisation, all convergents of the algorithm are best approximations (with one possible exception). We also provide a numerical example to illustrate the algorithm. 1 Introduction The best approximation of a line by lattice points is a problem of fundamental interest in the design of algorithms. The problem is one of finding those lattice points which lie successively closer to the given line as we move along the line away from the origin. That is, given an M-dimensional lattice\\Omega\\Gamma defined (though not un...