From prima quadraginta octant to lattice sphere through primitive integer operations.(English)Zbl 1338.68256
Summary: We present here the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. The algorithm evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences, which, in turn, aids in efficient computation. Each point of the lattice sphere is determined by resorting to only a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Detailed theoretical analysis and experimental results have been furnished to demonstrate its simplicity and elegance.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 11H06 | Lattices and convex bodies (number-theoretic aspects) |
Cite
Full Text:DOI
References:
| [1] | Andres, E., Discrete circles, rings and spheres, Computers & Graphics, 18, 5, 695-706 (1994) |
| [2] | Andres, E.; Jacob, M., The discrete analytical hyperspheres, IEEE Trans. Vis. Comput. Graph., 3, 1, 75-86 (1997) |
| [3] | Balog, A.; Bárány, I., On the convex hull of the integer points in a disc, (Proc. 7th Annual Symposium on Computational Geometry. Proc. 7th Annual Symposium on Computational Geometry, SoCG 1991 (1991)), 162-165 |
| [4] | Bera, S.; Bhowmick, P.; Bhattacharya, B. B., A digital-geometric algorithm for generating a complete spherical surface in \(Z^3\), (Proc. International Conference on Applied Algorithms. Proc. International Conference on Applied Algorithms, ICAA 2014. Proc. International Conference on Applied Algorithms. Proc. International Conference on Applied Algorithms, ICAA 2014, LNCS, vol. 8321 (2014)), 49-61 |
| [5] | Bera, S.; Bhowmick, P.; Stelldinger, P.; Bhattacharya, B. B., On covering a digital disc with concentric circles in \(Z^2\), Theoret. Comput. Sci., 506, 1-16 (2013) ·Zbl 1301.68235 |
| [6] | Bhowmick, P.; Bhattacharya, B. B., Number-theoretic interpretation and construction of a digital circle, Discrete Appl. Math., 156, 12, 2381-2399 (2008) ·Zbl 1143.68614 |
| [7] | Bhowmick, P.; Pal, S., Fast circular arc segmentation based on approximate circularity and cuboid graph, J. Math. Imaging Vision, 1-25 (2013) |
| [8] | Biswas, R.; Bhowmick, P., On finding spherical geodesic paths and circles in \(Z^3\), (Proc. 18th International Conference on Discrete Geometry for Computer Imagery. Proc. 18th International Conference on Discrete Geometry for Computer Imagery, DGCI 2014. Proc. 18th International Conference on Discrete Geometry for Computer Imagery. Proc. 18th International Conference on Discrete Geometry for Computer Imagery, DGCI 2014, LNCS, vol. 8668 (2014)), 396-409 ·Zbl 1417.68228 |
| [9] | Bresenham, J. E., A linear algorithm for incremental digital display of circular arcs, Commun. ACM, 20, 2, 100-106 (1977) ·Zbl 0342.68058 |
| [10] | Brimkov, V. E.; Barneva, R. P., Graceful planes and lines, Theoret. Comput. Sci., 283, 1, 151-170 (2002) ·Zbl 1050.68147 |
| [11] | Brimkov, V. E.; Barneva, R. P., Connectivity of discrete planes, Theoret. Comput. Sci., 319, 1-3, 203-227 (2004) ·Zbl 1068.52018 |
| [12] | Brimkov, V. E.; Barneva, R. P., On the polyhedral complexity of the integer points in a hyperball, Theoret. Comput. Sci., 406, 1-2, 24-30 (2008) ·Zbl 1151.52010 |
| [13] | Brimkov, V. E.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discrete Appl. Math., 155, 4, 468-495 (2007) ·Zbl 1109.68122 |
| [14] | Cappell, S. E.; Shaneson, J. L., Some problems in number theory I: the circle problem (2007) |
| [15] | Chamizo, F., Lattice points in bodies of revolution, Acta Arith., 85, 3, 265-277 (1998) ·Zbl 0919.11061 |
| [16] | Chamizo, F.; Cristobal, E., The sphere problem and the \(L\)-functions, Acta Math. Hungar., 135, 1-2, 97-115 (2012) ·Zbl 1294.11172 |
| [17] | Chamizo, F.; Cristóbal, E.; Ubis, A., Visible lattice points in the sphere, J. Number Theory, 126, 2, 200-211 (2007) ·Zbl 1132.11051 |
| [18] | Chamizo, F.; Cristóbal, E.; Ubis, A., Lattice points in rational ellipsoids, J. Math. Anal. Appl., 350, 1, 283-289 (2009) ·Zbl 1254.11092 |
| [19] | Chamizo, F.; Iwaniec, H., On the sphere problem, Rev. Mat. Iberoam., 11, 2, 417-429 (1995) ·Zbl 0837.11054 |
| [20] | Coeurjolly, D.; Sivignon, I.; Dupont, F.; Feschet, F.; Chassery, J.-M., On digital plane preimage structure, Discrete Appl. Math., 151, 1-3, 78-92 (2005) ·Zbl 1101.68900 |
| [21] | Cohen-Or, D.; Kaufman, A., Fundamentals of surface voxelization, Graph. Models Image Proc., 57, 6, 453-461 (1995) |
| [22] | Coxeter, H. S.M., Regular Polytopes (1973), Dover Publications ·Zbl 0031.06502 |
| [23] | Ewell, J. A., Counting lattice points on spheres, Math. Intelligencer, 22, 4, 51-53 (2000) ·Zbl 1052.11508 |
| [24] | Feschet, F.; Reveillès, J.-P., A generic approach for n-dimensional digital lines, (Proc. 13th International Conference on Discrete Geometry for Computer Imagery. Proc. 13th International Conference on Discrete Geometry for Computer Imagery, DGCI 2006. Proc. 13th International Conference on Discrete Geometry for Computer Imagery. Proc. 13th International Conference on Discrete Geometry for Computer Imagery, DGCI 2006, LNCS, vol. 4245 (2006)), 29-40 ·Zbl 1136.68570 |
| [25] | Fiorio, C.; Jamet, D.; Toutant, J.-L., Discrete circles: an arithmetical approach with non-constant thickness, (Vision Geometry XIV, Electronic Imaging, SPIE, vol. 6066 (2006)), 60660C |
| [26] | Fiorio, C.; Toutant, J.-L., Arithmetic discrete hyperspheres and separatingness, (Proc. 13th International Conference on Discrete Geometry for Computer Imagery. Proc. 13th International Conference on Discrete Geometry for Computer Imagery, DGCI 2006. Proc. 13th International Conference on Discrete Geometry for Computer Imagery. Proc. 13th International Conference on Discrete Geometry for Computer Imagery, DGCI 2006, LNCS, vol. 4245 (2006)), 425-436 ·Zbl 1136.68571 |
| [27] | Foley, J. D.; van Dam, A.; Feiner, S. K.; Hughes, J. F., Computer Graphics: Principles and Practice (1993), Addison-Wesley: Addison-Wesley Reading (Mass.) |
| [28] | Fomenko, O., Distribution of lattice points over the four-dimensional sphere, J. Math. Sci., 110, 6, 3164-3170 (2002) ·Zbl 1005.11043 |
| [29] | Heath-Brown, D. R., Lattice Points in the Sphere, Number Theory in Progress, vol. II, 883-892 (1999), Walter de Gruyter: Walter de Gruyter Berlin ·Zbl 0929.11040 |
| [30] | Honsberger, R., Circles, squares, and lattice points, (Mathematical Gems, vol. I (1973)), 117-127 |
| [31] | Kühleitner, M., On lattice points in rational ellipsoids: an omega estimate for the error term, Abh. Math. Semin. Univ. Hambg., 70, 1, 105-111 (2000) ·Zbl 1025.11032 |
| [32] | Kenmochi, Y.; Buzer, L.; Sugimoto, A.; Shimizu, I., Digital planar surface segmentation using local geometric patterns, (Proc. 14th International Conference on Discrete Geometry for Computer Imagery. Proc. 14th International Conference on Discrete Geometry for Computer Imagery, DGCI 2008. Proc. 14th International Conference on Discrete Geometry for Computer Imagery. Proc. 14th International Conference on Discrete Geometry for Computer Imagery, DGCI 2008, LNCS, vol. 4992 (2008)), 322-333 ·Zbl 1138.68599 |
| [33] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco ·Zbl 1064.68090 |
| [34] | Klette, R.; Rosenfeld, A., Digital straightness—a review, Discrete Appl. Math., 139, 1-3, 197-230 (2004) ·Zbl 1093.68656 |
| [35] | Kulikowski, T., Sur l’existence d’une sphère passant par un nombre donné aux coordonnées entières, L’Enseign. Math., 2, 89-90 (1959) ·Zbl 0109.03403 |
| [36] | Maehara, H., On a sphere that passes through \(n\) lattice points, European J. Combin., 31, 2, 617-621 (2010) ·Zbl 1186.68507 |
| [37] | Magyar, A., On the distribution of lattice points on spheres and level surfaces of polynomials, J. Number Theory, 122, 1, 69-83 (2007) ·Zbl 1119.11046 |
| [38] | Montani, C.; Scopigno, R., Spheres-to-voxels conversion, (Glassner, A. S., Graphics Gems (1990), Academic Press Professional, Inc.: Academic Press Professional, Inc. San Diego, CA, USA), 327-334 |
| [39] | Pal, S.; Bhowmick, P., Determining digital circularity using integer intervals, J. Math. Imaging Vision, 42, 1, 1-24 (2012) ·Zbl 1255.68262 |
| [40] | Pawlewicz, J.; Pătraşcu, M., Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons, Algorithmica, 55, 2, 271-282 (2009) ·Zbl 1191.68835 |
| [41] | Roget, B.; Sitaraman, J., Wall distance search algorithm using voxelized marching spheres, J. Comput. Phys., 241, 76-94 (2013) ·Zbl 1349.76643 |
| [42] | Schinzel, A., Sur l’existence d’un cercle passant par un nombre donné de points aux coordonnées entières, L’Enseign. Math., 2, 71-72 (1958) ·Zbl 0080.03401 |
| [43] | Sierpiński, W., A Selection of Problems in the Theory of Numbers (1964), Pergamon Press: Pergamon Press New York ·Zbl 0122.04401 |
| [44] | Sivignon, I.; Dupont, F.; Chassery, J.-M., Decomposition of a three-dimensional discrete object surface into discrete plane pieces, Algorithmica, 38, 1, 25-43 (2003) ·Zbl 1072.68118 |
| [45] | Toutant, J.-L.; Andres, E.; Roussillon, T., Digital circles, spheres and hyperspheres: from morphological models to analytical characterizations and topological properties, Discrete Appl. Math., 161, 16-17, 2662-2677 (2013) ·Zbl 1291.68412 |
| [46] | Tsang, K.-M., Counting lattice points in the sphere, Bull. Lond. Math. Soc., 32, 679-688 (2000) ·Zbl 1025.11033 |
| [47] | Vinogradov, I. M., On the number of integer points in a sphere, Izv. Ross. Akad. Nauk Ser. Mat., 27, 5, 957-968 (1963) ·Zbl 0116.03901 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
