Abstract
This paper presents a novel study on the functional gradation of coordinate planes in connection with the thinnest and tunnel-free (i.e., naive) discretization of sphere in the integer space. For each of the 48-symmetric quadraginta octants of naive sphere with integer radius and integer center, we show that the corresponding voxel set forms a bijection with its projected pixel set on a unique coordinate plane, which thereby serves as its functional plane. We use this fundamental property to prove several other theoretical results for naive sphere. First, the quadraginta octants form symmetry groups and subgroups with certain equivalent topological properties. Second, a naive sphere is always unique and consists of fewest voxels. Third, it is efficiently constructible from its functional-plane projection. And finally, a special class of 4-symmetric discrete 3D circles can be constructed on a naive sphere based on back projection from the functional plane.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A ‘jump’ here is synonymous with ‘mono-jump’ in the context of our work.
References
Aveneau, L., Andres, E., Mora, F.: Expressing discrete geometry using the conformal model. In: 5th Conference on Applied Geometric Algebras in Computer Science and Engineering (AGACSE’12). La Rochelle, France (2012). https://hal.archives-ouvertes.fr/hal-00865103
Aveneau, L., Fuchs, L., Andres, E.: Digital geometry from a geometric algebra perspective. In: 18th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI’14), Lecture Notes in Computer Science, vol. 8668, pp. 358–369. Siena, Italy (2014)
Biswas, R., Bhowmick, P.: On finding spherical geodesic paths and circles in \({\mathbb{{Z}}}^3\). In: 18th International Conference on Discrete Geometry for Computer Imagery (DGCI’14), Lecture Notes in Computer Science, vol. 8668, pp. 396–409. Siena, Italy (2014)
Biswas, R., Bhowmick, P.: On different topological classes of spherical geodesic paths and circles in \({\mathbb{{Z}}}^3\). Theoret. Comput. Sci. 605, 146–163 (2015)
Biswas, R., Bhowmick, P.: From prima quadraginta octant to lattice sphere through primitive integer operations. Theoret. Comput. Sci. 624, 56–72 (2016)
Biswas, R., Bhowmick, P.: On functionality of quadraginta octants of naive sphere with application to circle drawing. In: 19th International Conference on Discrete Geometry for Computer Imagery (DGCI’16), Lecture Notes in Computer Science, vol. 9647, pp. 256–267. Nantes, France (2016)
Biswas, R., Bhowmick, P., Brimkov, V.E.: On the connectivity and smoothness of discrete spherical circles. In: 17th International Workshop on Combinatorial Image Analysis (IWCIA’15), Lecture Notes in Computer Science, vol. 9448, pp. 86–100. Kolkata, India (2015)
Bresenham, J.E.: Algorithm for computer control of a digital plotter. IBM Syst. J. 4(1), 25–30 (1965)
Brimkov, V.E., Barneva, R.P.: Graceful planes and thin tunnel-free meshes. In: 8th International Conference on Discrete Geometry for Computer Imagery (DGCI’99), Lecture Notes in Computer Science, vol. 1568, pp. 53–64 (1999)
Brimkov, V.E., Barneva, R.P.: Graceful planes and lines. Theoret. Comput. Sci. 283(1), 151–170 (2002)
Brimkov, V.E., Barneva, R.P.: Connectivity of discrete planes. Theoret. Comput. Sci. 319(1–3), 203–227 (2004)
Brimkov, V.E., Barneva, R.P.: Plane digitization and related combinatorial problems. Discrete Appl. Math. 147(2–3), 169–186 (2005)
Brimkov, V.E., Coeurjolly, D., Klette, R.: Digital planarity—a review. Discrete Appl. Math. 155(4), 468–495 (2007)
Cohen-Or, D., Kaufman, A.: Fundamentals of surface voxelization. Graph. Models Image Process. 57(6), 453–461 (1995)
Cohen-Or, D., Kaufman, A.: 3D line voxelization and connectivity control. IEEE Comput. Graph. Appl. 17(6), 80–87 (1997)
Gouraud, H.: Continuous shading of curved surfaces. IEEE Trans. Comput. 20(6), 623–629 (1971)
Kaufman, A.: Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. SIGGRAPH Comput. Graph. 21(4), 171–179 (1987)
Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004)
Mukhopadhyay, J., Das, P.P., Chattopadhyay, S., Bhowmick, P., Chatterji, B.N.: Digital Geometry in Image Processing. CRC, Boca Raton (2013)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this work was presented in DGCI’16 [6].
Appendix: Notations for C-octants and Q-octants
Appendix: Notations for C-octants and Q-octants
C-oct | Q-octants | Notation |
|---|---|---|
\({\mathbb {C}}_{1}\) | \({\mathbb {Q}}_{1},\ldots ,{\mathbb {Q}}_{6}\) | \(+++\) |
\({\mathbb {C}}_{2}\) | \({\mathbb {Q}}_{7},\ldots ,{\mathbb {Q}}_{12}\) | \(-++\) |
\({\mathbb {C}}_{3}\) | \({\mathbb {Q}}_{13},\ldots ,{\mathbb {Q}}_{18}\) | \(+-+\) |
\({\mathbb {C}}_{4}\) | \({\mathbb {Q}}_{19},\ldots ,{\mathbb {Q}}_{24}\) | \({-}{-}+\) |
\({\mathbb {C}}_{5}\) | \({\mathbb {Q}}_{25},\ldots ,{\mathbb {Q}}_{30}\) | \(++-\) |
\({\mathbb {C}}_{6}\) | \({\mathbb {Q}}_{31},\ldots ,{\mathbb {Q}}_{36}\) | \(-+-\) |
\({\mathbb {C}}_{7}\) | \({\mathbb {Q}}_{37},\ldots ,{\mathbb {Q}}_{42}\) | \(+{-}{-}\) |
\({\mathbb {C}}_{8}\) | \({\mathbb {Q}}_{43},\ldots ,{\mathbb {Q}}_{48}\) | \({-}{-}{-}\) |
Q-oct | Notation | Q-oct | Notation | Q-oct | Notation |
|---|---|---|---|---|---|
\({\mathbb {Q}}_{1}\) | \((+1, +2, +3)\) | \({\mathbb {Q}}_{2}\) | \((+2, +1, +3)\) | \({\mathbb {Q}}_{3}\) | \((+2, +3, +1)\) |
\({\mathbb {Q}}_{7}\) | \((-1, +2, +3)\) | \({\mathbb {Q}}_{8}\) | \((+2, -1, +3)\) | \({\mathbb {Q}}_{9}\) | \((+2, +3, -1)\) |
\({\mathbb {Q}}_{13}\) | \((+1, -2, +3)\) | \({\mathbb {Q}}_{14}\) | \((-2, +1, +3)\) | \({\mathbb {Q}}_{15}\) | \((-2, +3, +1)\) |
\({\mathbb {Q}}_{19}\) | \((-1, -2, +3)\) | \({\mathbb {Q}}_{20}\) | \((-2, -1, +3)\) | \({\mathbb {Q}}_{21}\) | \((-2, +3, -1)\) |
\({\mathbb {Q}}_{25}\) | \((+1, +2, -3)\) | \({\mathbb {Q}}_{26}\) | \((+2, +1, -3)\) | \({\mathbb {Q}}_{27}\) | \((+2, -3, +1)\) |
\({\mathbb {Q}}_{31}\) | \((-1, +2, -3)\) | \({\mathbb {Q}}_{32}\) | \((+2, -1, -3)\) | \({\mathbb {Q}}_{33}\) | \((+2, -3, -1)\) |
\({\mathbb {Q}}_{37}\) | \((+1, -2, -3)\) | \({\mathbb {Q}}_{38}\) | \((-2, +1, -3)\) | \({\mathbb {Q}}_{39}\) | \((-2, -3, +1)\) |
\({\mathbb {Q}}_{43}\) | \((-1, -2, -3)\) | \({\mathbb {Q}}_{44}\) | \((-2, -1, -3)\) | \({\mathbb {Q}}_{45}\) | \((-2, -3, -1)\) |
Q-oct | Notation | Q-oct | Notation | Q-oct | Notation |
|---|---|---|---|---|---|
\({\mathbb {Q}}_{4}\) | \((+3, +2, +1)\) | \({\mathbb {Q}}_{5}\) | \((+3, +1, +2)\) | \({\mathbb {Q}}_{6}\) | \((+1, +3, +2)\) |
\({\mathbb {Q}}_{10}\) | \((+3, +2, -1)\) | \({\mathbb {Q}}_{11}\) | \((+3, -1, +2)\) | \({\mathbb {Q}}_{12}\) | \((-1, +3, +2)\) |
\({\mathbb {Q}}_{16}\) | \((+3, -2, +1)\) | \({\mathbb {Q}}_{17}\) | \((+3, +1, -2)\) | \({\mathbb {Q}}_{18}\) | \((+1, +3, -2)\) |
\({\mathbb {Q}}_{22}\) | \((+3, -2, -1)\) | \({\mathbb {Q}}_{23}\) | \((+3, -1, -2)\) | \({\mathbb {Q}}_{24}\) | \((-1, +3, -2)\) |
\({\mathbb {Q}}_{28}\) | \((-3, +2, +1)\) | \({\mathbb {Q}}_{29}\) | \((-3, +1, +2)\) | \({\mathbb {Q}}_{30}\) | \((+1, -3, +2)\) |
\({\mathbb {Q}}_{34}\) | \((-3, +2, -1)\) | \({\mathbb {Q}}_{35}\) | \((-3, -1, +2)\) | \({\mathbb {Q}}_{36}\) | \((-1, -3, +2)\) |
\({\mathbb {Q}}_{40}\) | \((-3, -2, +1)\) | \({\mathbb {Q}}_{41}\) | \((-3, +1, -2)\) | \({\mathbb {Q}}_{42}\) | \((+1, -3, -2)\) |
\({\mathbb {Q}}_{46}\) | \((-3, -2, -1)\) | \({\mathbb {Q}}_{47}\) | \((-3, -1, -2)\) | \({\mathbb {Q}}_{48}\) | \((-1, -3, -2)\) |
Rights and permissions
About this article
Cite this article
Biswas, R., Bhowmick, P. On the Functionality and Usefulness of Quadraginta Octants of Naive Sphere. J Math Imaging Vis 59, 69–83 (2017). https://doi.org/10.1007/s10851-017-0718-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-017-0718-4