DISCRETE CONVEXITY, STRAIGHTNESS, AND THE 16-NEIGHBORHOOD

In this paper, we extend some results in discrete geometry based on th e 8-neighborhood to that of the 16-neighborhood, which now includes th e chessboard and the knight moves. We first present some analogies bet ween an 8-digital are and a 16-digital are as represented by shortest paths on the grid. We present a transformation which uniquely maps a 1 6-digital are onto an 8-digital are (and vice versa). The grid-interse ct-quantization (GIQ) of real arcs is defined with the M-neighborhood. This enables us to define a M-digital straight segment. We then prese nt two new distance functions which satisfy the metric properties and describe the extended neighborhood space. Based on these functions, we present some new results regarding discrete convexity and 16-digital straightness. In particular, we demonstrate the convexity of a 16-digi tal straight segment. Moreover, we define a new property for character izing a digital straight segment in the 16-neighborhood space. In comp arison to the 8-neighborhood space, the proposed 16-neighborhood codin g scheme offers a more compact representation without any loss of info rmation. (C) 1997 Academic Press.