Finding well approximating lattices for a finite set of points

Abstract

In this paper we address the problem of finding well approximating lattices for a given finite set $A$ of points in ${\mathbb{R}}^n$. More precisely, we search for $\check{o},\check{d_1},\dots ,\check{d_n}\in {\mathbb{R}}^n$ such that $\check{a}-\check{o}$ is close to $\Lambda =\check{d_1}\mathbb{Z}+\cdots +\check{d_n}\mathbb{Z}$ for every $\check{a}\in A$. First we deal with the one-dimensional case, where we show that in a sense the results are almost the best possible. These results easily extend to the multi-dimensional case where the directions of the axes are given, too. Thereafter we treat the general multi-dimensional case. Our method relies on the LLL algorithm. Finally we apply the least squares algorithm to optimize the results. We give several examples to illustrate our approach.