On disks of the triangular grid: An application of optimization theory in discrete geometry

Abstract

Chamfer (or weighted) distances are popular digital distances used in various grids. They are based on the weights assigned to steps to various neighborhoods. In the triangular grid there are three usually used neighbor relations, consequently, chamfer distances based on three weights are used. A chamfer (or digital) disk of a grid is the set of the pixels which have distance from the origin that is not more than a given finite bound called radius. These disks are well known and well characterized on the square grid. Using the two basic (i.e., the cityblock and the chessboard) neighbors, the convex hull of a disk is always an octagon (maybe degenerated). Recently, these disks have been defined on the triangular grid; their shapes have a great variability even with the traditional three type of neighbors, but their complete characterization is still missing. Chamfer balls are convex hulls of integer points that lie in polytopes defined by linear inequalities, and thus can be computed through a linear integer programming approach. 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. In this paper, sides of the chamfer disks are determined by the inequalities with their Chvatal rank 1. The most popular coordinate system of the triangular grid uses three coordinates. By giving conditions depending only a coordinate, the embedding hexagons of the shapes are obtained. These individual bounds are described completely by Chvatal cuts. They also give the complete description of some disks. Further inequalities having Chvatal rank 1 are also discussed. (C) 2019 Elsevier B.V. All rights reserved.