Finding well approximating lattices for a finite set of points

DOI10.1090/MCOM/3320MaRDI QIDQ4683170zbMATH OpenOpenAlexFDO

Authors András Hajdu, Lajos Hajdu, R. Tijdeman

Publication date 20 September 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.05989

zbMATH Keywords

Diophantine approximationlatticeleast squares algorithmLLL algorithm

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Simultaneous homogeneous approximation, linear forms (11J13)

Abstract: In this paper we address the problem of finding well approximating lattices for a given finite set $A$ of points in ${mathbbR}^n$. More precisely, we search for $vo,v{d}_1,dots,v{d}_{n}inmathbb{R}^n$ such that $va-vo$ is close to $Lambda=v{d}_{1}mathbbZ+dots+v{d}_{n}mathbbZ$ for every $vainA$. 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.

Recommendations

• Finding the closest lattice point by iterative slicing
• Closest point search in lattices
• scientific article; zbMATH DE number 3908520
• scientific article; zbMATH DE number 5532102
• Finding a closest point in a lattice of Voronoi's first kind

Cites work

• Approximate common divisors via lattices
• Diophantine approximation
• Factoring polynomials with rational coefficients
• Fascinating quasicrystals
• Finding simultaneous Diophantine approximations with prescribed quality
• scientific article; zbMATH DE number 3125787 (Why is no real title available?)
• scientific article; zbMATH DE number 1852136 (Why is no real title available?)

Cited in

(3)

• A best lower bound for good lattice points
• A fast algorithm for determining the distances of the points of a given set in an integral lattice from its complement
• Detecting periodicity in digital images by the LLL algorithm

This page was built for publication: Finding well approximating lattices for a finite set of points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4683170)