An Integer Programming Approach to Characterize Digital Disks on the Triangular Grid

Abstract

Generally, the integer hull of a polyhedral set is the convex hull of the integer points of the set. In most of the cases, for example when the set is bounded, the integer hull is a polyhedral set, as well. The integer hull can be determined in an iterative way by Chvatal cuts. Weighted (or chamfer) distances are popular digital distances used in various grids. They are based on the weights assigned to steps to various neighborhood. In the triangular grid there are three usually used neighborhood, consequently, chamfer distances based on three weights are defined. A digital disk (or a chamfer ball) of a grid is the set of the elements which are not on a longer distance from the origin than a given finite bound, radius. These disks are well known and well characterized on the square grid (with even larger neighborhood than the usual 3x3), and recently they become a topic of a current research on the triangular grid. The shapes of the disks in the latter case have a great variability. In this paper, the inequalities satisfied by the elements of a disk are analyzed if their Chvatal rank is 1. The most popular coordinate system of the triangular grid uses three coordinates. Individual bounds are described completely. It also gives the complete description of some disks. Further inequalities having Chvatal rank 1 are also discussed.