| Autor: |
Harrison, Anthony, Soprunova, Jenya |
| Rok vydání: |
2017 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
The lattice size of a lattice polytope $P$ was defined and studied by Schicho, and Castryck and Cools. They provided an "onion skins" algorithm for computing the lattice size of a lattice polygon $P$ in $\mathbb{R}^2$ based on passing successively to the convex hull of the interior lattice points of $P$. We explain the connection of the lattice size to the successive minima of $K=\left(P+(-P)\right)^\ast$ and to the lattice reduction with respect to the general norm that corresponds to $K$. It follows that the generalized Gauss algorithm of Kaib and Schnorr (which is faster than the "onion skins" algorithm) computes the lattice size of any convex body in $\mathbb{R}^2$. We extend the work of Kaib and Schnorr to dimension 3, providing a fast algorithm for lattice reduction with respect to the general norm defined by a convex origin-symmetric body $K\subset\mathbb{R}^3$. We also explain how to recover the successive minima of $K$ and the lattice size of $P$ from the obtained reduced basis and therefore provide a fast algorithm for computing the lattice size of any convex body $P\subset\mathbb{R}^3$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
