The Number of Different Digital N-Discs

Abstract

Configurations of integer lattice points inside a closed curve are a permanent topic in different research areas: from number theory to digital image analysis. This paper deals with the digital N-discs—the sets consisting of N integer lattice points which fall inside a circle. A digital N-disc corresponds to a digital image of a real circular discs, which consists of N pixels. We show that, for a large positive integer N, the average number of digital N-discs is asymptotic to 2N when N runs through a set of intervals, whose length is upper bounded by N47 / 58. In addition, we show that 2N is the best possible asymptotic estimate (the error term is ignored), for the number of digital N-discs. Such an asymptotic estimate is reached for almost all digital N-discs, for N in an interval, of the length N47 / 58. This improves result of Huxley and Žunić (IEEE Trans Pattern Anal Mach Intell 29:159–161, 2007), where an O(N) upper bound, for the number of digital N-discs, has been proven.