On finding spherical geodesic paths and circles in \(\mathbb Z^{3}\).(English)Zbl 1417.68228
Barcucci, Elena (ed.) et al., Discrete geometry for computer imagery. 18th IAPR international conference, DGCI 2014, Siena, Italy, September 10–12, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8668, 396-409 (2014).
Summary: A discrete spherical geodesic path between two voxels \(s\) and \(t\) lying on a discrete sphere is a/the 1-connected shortest path from \(s\) to \(t\), comprising voxels of the discrete sphere intersected by the real plane passing through \(s, t\), and the center of the sphere. We show that the set of sphere voxels intersected by the aforesaid real plane always contains a 1-connected cycle passing through \(s\) and \(t\), and each voxel in this set lies within an isothetic distance of \(\frac32\) from the concerned plane. Hence, to compute the path, the algorithm starts from \(s\), and iteratively computes each voxel \(p\) of the path from the predecessor of \(p\). A novel number-theoretic property and the 48-symmetry of discrete sphere are used for searching the 1-connected voxels comprising the path. The algorithm is output-sensitive, having its time and space complexities both linear in the length of the path. It can be extended for constructing 1-connected discrete 3D circles of arbitrary orientations, specified by a few appropriate input parameters. Experimental results and related analysis demonstrate its efficiency and versatility.
For the entire collection see [Zbl 1295.68017].
For the entire collection see [Zbl 1295.68017].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Cite
Full Text:DOI
