Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Finding well approximating lattices for a finite set of points


Authors: A. Hajdu, L. Hajdu and R. Tijdeman
Journal: Math. Comp. 88 (2019), 369-387
MSC (2010): Primary 11J13, 11H06
DOI: https://doi.org/10.1090/mcom/3320
Published electronically: April 5, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11J13, 11H06

Retrieve articles in all journals with MSC (2010): 11J13, 11H06


Additional Information

A. Hajdu
Affiliation: Faculty of Informatics, University of Debrecen P.O. Box 12, H-4010 Debrecen, Hungary
Email: hajdu.andras@inf.unideb.hu

L. Hajdu
Affiliation: Institute of Mathematics, University of Debrecen P.O. Box 12, H-4010 Debrecen, Hungary
Email: hajdul@science.unideb.hu

R. Tijdeman
Affiliation: Mathematical Institute, Leiden University Postbus 9512, 2300 RA Leiden, The Netherlands
Email: tijdeman@math.leidenuniv.nl

DOI: https://doi.org/10.1090/mcom/3320
Keywords: Diophantine approximation, lattice, LLL algorithm, least squares algorithm
Received by editor(s): April 9, 2016
Received by editor(s) in revised form: January 11, 2017, and August 6, 2017
Published electronically: April 5, 2018
Additional Notes: This research was supported in part by the OTKA grants K100339, NK101680, K115479 and the projects TÁMOP-4.2.2.C-11/1/KONV-2012-0001, EFOP-3.6.2-16-2017-00015 and VKSZ_14-1-2015-0072, SCOPIA: Development of diagnostic tools based on endoscope technology supported by the European Union, co-financed by the European Social Fund.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society