Finding well approximating lattices for a finite set of points

Abstract:

In this paper we address the task of finding well approximating lattices for a given finite set $A$ of points in ${\mathbb R}^n$ motivated by practical texture analytic problems. More precisely, we search for $\boldsymbol {o},\boldsymbol {d_1}, \dots ,\boldsymbol {d_n}\in \mathbb {R}^n$ such that $\boldsymbol {a}-\boldsymbol {o}$ is close to $\Lambda =\boldsymbol {d_1}\mathbb {Z}+\dots +\boldsymbol {d_n}\mathbb {Z}$ for every $\boldsymbol {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.