Disc Cover in ℤ2
(Characterization by number theory and digital geometry)Algorithm
S. Bera, P. Bhowmick, P. Stelldinger, and B. B. Bhattacharya,
On Covering a Digital Disc with Concentric Circles in ℤ2,
Theoretical Computer Science, Vol. 506, pp. 1-16, 2013.
What, Why, How
Digital circles and digital discs satisfy many bizarre anisotropic properties, understanding of which is essential for solving various problems in image analysis and computer graphics. We unveil the underlying properties of absentee pixels that appear while covering a digital disc with concentric digital circles. We present, for the first time, a mathematical characterization of these pixels based on number theory and digital geometry. Interestingly, the absentees occur in multitude, and we show that their count varies quadratically with the radius. The notion of infimum parabola and supremum parabola has been used to derive the count of these absentees. Using this parabolic characterization, we derive a necessary and sufficient condition for a pixel to be a disc absentee, and obtain the geometric properties of the absentees. An efficient algorithm to locate the absentees is also designed. We show that the ratio of the absentee pixels to the total number of disc pixels approaches a constant with increasing radius. Exhaustive test results substantiate our theoretical findings.
Absentees (red) for r = 20 while covering a digital disc by circle pixels (gray) in ℤ2.
Main Results
We present here only some illustrations just showing how to fix the absentees.
Absentee Intervals
Figure below shows the intervals (red) in which absentees lie.
The light-gray intervals correspond to radius r+1, and the deep-gray intervals to radius r.
These intervals follow interesting recurrences, which are easy to compute.
The abscissa of each absentee is contained only in these intervals.
Absentee Parabolas
Figure below shows the parabolas containing the absentees corresponding to circles
up to radius 20 (pointed by blue arrows). Octant 1 is made bright while other seven octants are dimmed.
Parabolic Characterization
Figure below shows the parabolic characterization of the absentee pixels in all eight octants.
The absentees up to radius 20 are shown by blue arrows.
Infimum parabolas are shown in black and supremum parabolas in red.
Algorithm
