On Finding Spherical Geodesic Paths and Circles in ℤ3
Biswas, Ranita
Bhowmick, Partha
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 32 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.
Springer
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/5810
Biswas R, Bhowmick P. On Finding Spherical Geodesic Paths and Circles in ℤ3. 2014;8668:396-409. doi:<a href="https://doi.org/10.1007/978-3-319-09955-2_33">10.1007/978-3-319-09955-2_33</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-09955-2_33
info:eu-repo/semantics/altIdentifier/issn/0302-9743
info:eu-repo/semantics/altIdentifier/issn/1611-3349
info:eu-repo/semantics/altIdentifier/isbn/9783642387081
info:eu-repo/semantics/altIdentifier/isbn/9783642387098
info:eu-repo/semantics/closedAccess