The Number of N-Point Digital Discs
|
A digital disc is the set of all integer points inside some given disc. Let {\cal D}_{N} be the number of different digital discs consisting of N points (different up to translation). The upper bound {\cal D}_{N} = {\cal O}(N^{2}) was shown recently; no corresponding lower bound is known. In this paper, we refine the upper bound to {\cal D}_{N} = {\cal O}(N), which seems to be the true order of magnitude, and we show that the average \overline{\cal D}_{N} = \left({\cal D}_{1} + {\cal D}_{2} + \ldots + {\cal D}_{N}\right)/N has upper and lower bounds which are of polynomial growth in N.
[1] 159 C. Berenstein and D. Lavine, “On the Number of Digital Straight Line Segments,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, pp.880-887, 1988.
[2] S. Fisk, “Separating Point Sets by Circles, and the Recognition of Digital Discs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 554-556, 1984.
[3] M.N. Huxley, “Area, Lattice Points, and Exponential Sums,” London Math. Soc. Monographs 13, Oxford Univ. Press, 1996.
[4] M.N. Huxley, “Exponential Sums and Lattice Points III,” Proc. London Math. Soc., vol. 87, pp. 591-609, 2003.
[5] M.N. Huxley and J. Žunić, “Different Digitizations of Displaced Discs,” Foundations of Computational Math., vol. 6, pp. 255-268, 2006.
[6] D.G. Kendall, “On the Number of Lattice Points Inside a Random Oval,” Quarterly J. Math., vol. 19, pp. 1-26, 1948.
[7] C.E. Kim, “Digital Circles,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 372-374, 1984.
[8] R. Klette and J. Žunić, “Multigrid Convergence of Calculated Features in Image Analysis,” J. Math. Imaging and Vision, vol. 13, pp. 173-191, 2000.
[9] R. Klette and A. Rosenfeld, Digital Geometry. Morgan Kaufman, 2004.
[10] E. Krätzel, Lattice Points. VEB Deutscher Verlag der Wissenschaften, 1988.
[11] J. Koplowitz, M. Lindenbaum, and A. Bruckstein, “On the Number of Digital Straight Lines on a Squared Grid,” IEEE Trans. Information Theory, vol. 15, pp. 949-953, 1993.
[12] S.X. Liao and M. Pawlak, “On the Accuracy of Zernike Moments for Image Analysis,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, pp.1358-1364, 1998.
[13] M. Pawlak and S.X. Liao, “On the Recovery of a Function on a Circular Domain,” IEEE Trans. Information Theory, vol. 48, pp. 2736-2753, 2002.
[14] M. Worring and A.W.M. Smeulders, “Digitized Circular Arcs: Characterization and Parameter Estimation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 587-598, 1995.
[15] J. Žunić, “On the Number of Digital Discs,” J. Math. Imaging and Vision, vol. 21, pp. 199-204, 2004.
[16] J. Žunić and N. Sladoje, “Efficiency of Characterizing Ellipses and Ellipsoids by Discrete Moments,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, pp. 407-414, 2000.
Index Terms:
Digital disc, digitization, enumeration, digital geometry.
Citation:
Martin N. Huxley, Joviša Žunić, "The Number of N-Point Digital Discs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 159-161, Jan. 2007, doi:10.1109/TPAMI.2007.20
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb