The Exact Lattice Width of Planar Sets and Minimal Arithmetical Thickness

摘要

We provide in this paper an algorithm for the exact computation of the lattice width of an integral polygon K with n vertices in O(n log s) arithmetic operations where s is a bound on all integers defining vertices and edges. We also provide an incremental version of the algorithm whose update complexity is shown to be O(log n + log s). We apply this algorithm to construct the arithmetical line with minimal thickness, which contains a given set of integer points.