Improved bounds on the diameter of lattice polytopes |
| |
Authors: | A. Deza L. Pournin |
| |
Affiliation: | 1.McMaster University,Ontario,Canada;2.Université de Paris Sud,Orsay,France;3.LIPN,Villetaneuse,France |
| |
Abstract: | We show that the largest possible diameter ({delta(d,k)}) of a d-dimensional polytope whose vertices have integer coordinates ranging between 0 and k is at most ({kd - lceil2d/3rceil-(k-3)}) when ({kgeq3}) . In addition, we show that ({delta(4,3)=8}) . This substantiates the conjecture whereby ({delta(d,k)}) is at most ({lfloor(k+1)d/2rfloor}) and is achieved by a Minkowski sum of lattice vectors. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|