Affiliations: Computer Science & Engineering Department, Indian
Institute of Technology, Kharagpur, India. pb@cse.iitkgp.ernet.in,
bhowmick@gmail.com | Advanced Computing & Microelectronics Unit, Indian
Statistical Institute, Kolkata, India. bhargab@isical.ac.in
Note: [] Address for correspondence Computer Science and Engineering
Department, Indian Institute of Technology, Kharagpur 721302, India
Abstract: There are several algorithms for digitization of a real disc
(circle) to derive a digital disc, and also for finding the real disc
corresponding to a digital disc. However, the correspondence of a digital disc
with a regular polygon in the real plane is not well studied. This paper
presents some theories and related experiments on setting the correspondence
from a digital disc to its polygonal cover in the real plane. For an ideal
regular polygon covering a digital disc, all the grid points of the digital
disc should lie on and inside the polygon, and vice versa. That an ideal
regular polygon corresponding to a digital disc is possible for some of the
digital discs, especially for the ones having smaller radii, is shown. Further,
for a disc whose ideal regular polygon is not possible, an approximate polygon,
tending to the ideal one, is possible, in which the error of approximation can
be controlled by the number of vertices of the approximate polygon. These
(ideal or approximate) polygonal covers of digital discs have several
applications in many problems of point set pattern matching. We have reported
the conditions under which an ideal regular polygon always exists corresponding
to a digital disc, and the conditions under which the existence of an ideal
regular polygon becomes uncertain. Experimental results have been given to
demonstrate the possibilities of approximation and the trade-off in terms of
error versus the number of vertices in the approximate polygon.
Keywords: digital disc, digital circle, polygonal approximation, digital geometry
