On different topological classes of spherical geodesic paths and circles in \(\mathbb{Z}^3\).(English)Zbl 1337.53048
Summary: Adiscrete spherical geodesic path (DSGP) between two voxels \(s\) and \(t\) lying on a discrete sphere is a/the shortest path from \(s\) to \(t\), comprising voxels of the discrete sphere intersected by the discrete geodesic plane passing through \(s\), \(t\), and the center of the sphere. We consider two classes of discretization, namelynaive andstandard, for both the sphere and the geodesic plane, which gives rise to four distinct topological classes of DSGP. We show that thenaive-naive class does not guarantee the existence of a DSGP, whereas the other three classes do. We derive the upper bounds of the distance of a DSGP belonging to each class, from the real sphere and the real plane, for different neighborhood conditions. We propose an efficient integer-based algorithm to compute the DSGP for any class-and-neighborhood combination. Novel number-theoretic characterization of discrete sphere has been used for searching the voxels comprising a DSGP. The algorithm isoutput-sensitive, having its time and space complexities both linear in the length of the DSGP. It can also be extended for constructing discrete 3D circles of arbitrary orientations, specified by a few appropriate input parameters. Experimental results and related analysis demonstrate its efficiency and versatility.
MSC:
| 53C22 | Geodesics in global differential geometry |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Cite
Full Text:DOI
References:
| [1] | Andres, E.; Acharya, R.; Sibata, C., Discrete analytical hyperplanes, Graph. Models Image Process., 59, 5, 302-309 (1997) |
| [2] | Andres, E.; Jacob, M., The discrete analytical hyperspheres, IEEE Trans. Vis. Comput. Graph., 3, 1, 75-86 (1997) |
| [3] | Balasubramanian, M.; Polimeni, J. R.; Schwartz, E. L., Exact geodesics and shortest paths on polyhedral surfaces, IEEE Trans. Pattern Anal. Mach. Intell., 31, 6, 1006-1016 (2009) |
| [4] | Biswas, R.; Bhowmick, P., On finding spherical geodesic paths and circles in \(Z^3\), (18th International Conference on Discrete Geometry for Computer Imagery. 18th International Conference on Discrete Geometry for Computer Imagery, LNCS, vol. 8668 (2014)), 396-409 ·Zbl 1417.68228 |
| [5] | Brimkov, V., Formulas for the number of \((n - 2)\)-gaps of binary objects in arbitrary dimension, Discrete Appl. Math., 157, 3, 452-463 (2009) ·Zbl 1168.68048 |
| [6] | Brimkov, V. E.; Barneva, R. P., Graceful planes and thin tunnel-free meshes, (8th International Conference on Discrete Geometry for Computer Imagery. 8th International Conference on Discrete Geometry for Computer Imagery, LNCS, vol. 1568 (1999)), 53-64 ·Zbl 0933.68139 |
| [7] | Brimkov, V. E.; Barneva, R. P., Graceful planes and lines, Theoret. Comput. Sci., 283, 1, 151-170 (2002) ·Zbl 1050.68147 |
| [8] | Brimkov, V. E.; Barneva, R. P., Connectivity of discrete planes, Theoret. Comput. Sci., 319, 1-3, 203-227 (2004) ·Zbl 1068.52018 |
| [9] | Brimkov, V. E.; Barneva, R. P., Plane digitization and related combinatorial problems, Discrete Appl. Math., 147, 2-3, 169-186 (2005) ·Zbl 1068.68111 |
| [10] | 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 |
| [11] | Brimkov, V. E.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discrete Appl. Math., 155, 4, 468-495 (2007) ·Zbl 1109.68122 |
| [12] | Bulow, T.; Klette, R., Digital curves in 3D space and a linear-time length estimation algorithm, IEEE Trans. Pattern Anal. Mach. Intell., 24, 7, 962-970 (2002) |
| [13] | Chen, J.; Han, Y., Shortest paths on a polyhedron, (6th Annual Symposium on Computational Geometry (1990)), 360-369 |
| [14] | Coeurjolly, D.; Miguet, S.; Tougne, L., 2D and 3D visibility in discrete geometry: an application to discrete geodesic paths, Pattern Recogn. Lett., 25, 5, 561-570 (2004) |
| [15] | Cohen-Or, D.; Kaufman, A., Fundamentals of surface voxelization, Graph. Models Image Process., 57, 6, 453-461 (1995) |
| [16] | Coxeter, H. S.M., Regular Polytopes (1973), Dover Publications ·Zbl 0031.06502 |
| [17] | Fiorio, C.; Toutant, J.-L., Arithmetic discrete hyperspheres and separatingness, (13th International Conference on Discrete Geometry for Computer Imagery. 13th International Conference on Discrete Geometry for Computer Imagery, LNCS, vol. 4245 (2006)), 425-436 ·Zbl 1136.68571 |
| [18] | Kimmel, R.; Sethian, J. A., Computing geodesic paths on manifolds, (Proceedings of the National Academy of Sciences of the United States of America. Proceedings of the National Academy of Sciences of the United States of America, Applied Mathematics, vol. 95 (1998)), 8431-8435 ·Zbl 0908.65049 |
| [19] | Kishan, H., Vector Algebra and Calculus (2008), Atlantic: Atlantic New Delhi, India |
| [20] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco ·Zbl 1064.68090 |
| [21] | Li, F.; Klette, R., Analysis of the rubberband algorithm, Image Vis. Comput., 25, 10, 1588-1598 (2007) |
| [22] | Martínez, D.; Velho, L.; Carvalho, P. C., Computing geodesics on triangular meshes, Computers & Graphics, 29, 5, 667-675 (2005) |
| [23] | Mitchell, J. S.B.; Mount, D. M.; Papadimitriou, C. H., The discrete geodesic problem, SIAM J. Comput., 16, 4, 647-668 (1987) ·Zbl 0625.68051 |
| [24] | Polthier, K.; Schmies, M., Straightest geodesics on polyhedral surfaces, (ACM SIGGRAPH 2006 Courses (2006)), 30-38 |
| [25] | Surazhsky, V.; Surazhsky, T.; Kirsanov, D.; Gortler, S. J.; Hoppe, H., Fast exact and approximate geodesics on meshes, ACM Trans. Graph., 24, 3, 553-560 (2005) |
| [26] | 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 |
| [27] | Xin, S.-Q.; Wang, G.-J., Improving Chen and Han’s algorithm on the discrete geodesic problem, ACM Trans. Graph., 28, 4, 104:1-104:8 (2009) |
| [28] | Xin, S.-Q.; Ying, X.; He, Y., Constant-time all-pairs geodesic distance query on triangle meshes, (ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (2012)), 31-38 |
| [29] | Ying, X.; Wang, X.; He, Y., Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem, ACM Trans. Graph., 32, 6, 170:1-170:12 (2013) |
| [30] | Ying, X.; Xin, S.-Q.; He, Y., Parallel Chen-Han (PCH) algorithm for discrete geodesics, ACM Trans. Graph., 33, 1, 9:1-9:11 (2014) ·Zbl 1288.68235 |
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.
