Finding well approximating lattices for a finite set of points
András Hajdú, Lajos Hajdu, Rob Tijdeman · Mathematics of Computation · 2017
In this paper we address the task of finding well approximating lattices for a given finite set A A of points in R n {\mathbb R}^n motivated by practical texture analytic problems. More precisely, we search for o , d 1 , … , d n ∈ R n \boldsymbol {o},\boldsymbol {d_1}, \dots ,\boldsymbol {d_n}\in \mathbb {R}^n such that a − o \boldsymbol {a}-\boldsymbol {o} is close to Λ = d 1 Z + ⋯ + d n Z \Lambda =\boldsymbol {d_1}\mathbb {Z}+\dots +\boldsymbol {d_n}\mathbb {Z} for every a ∈ A \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.