Topology of Spherical Geodesics in $\zzz$Different classes and their characterizationAlgorithmRanita Biswas and Partha Bhowmick,On Different Topological Classes of Spherical Geodesic Paths and Circles in $\zzz$, Theoretical Computer Science, Vol. 605, pp. 146–163, 2015. ContributionA discrete 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, namely naive and standard, for both the sphere and the geodesic plane, which gives rise to four distinct topological classes of DSGP.We show that the naivenaive (NN) class does not guarantee the existence of a DSGP, whereas the other three classes (NS, SN, SS) 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 integerbased algorithm to compute the DSGP for any classandneighborhood combination. Novel numbertheoretic characterization of discrete sphere has been used for searching the voxels comprising a DSGP. The algorithm is outputsensitive, 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. 

To construct an $l$connected DSGP from a voxel $s\in\ds{m}$ to a voxel $t\in\ds{m}$,
the algorithm iteratively computes the set of voxels that are $l$connected to $s$,
belong to $\dsrp{m,n}{s,t}$, and ensure the direction towards $t$.
Then it executes a PrioritizedBFS to get a/the $l$connected shortest path while
minimizing its maximum isothetic distance from $\rp{s,t}$.
The adjacency list $L$ of the underlying undirected graph $G(V,E)$ is prepared
based on $l$adjacency of the voxels in $\dsrp{m,n}{s,t}$.
The list $L$ is not prepared for the entire set $\dsrp{m,n}{s,t}$ but only for
the part of $\dsrp{m,n}{s,t}$ starting from $s$ and ending at $t$.
The voxels adjacent to each voxel $p\in V$ are inserted in the adjacency chain
$L[p]$ of $p$ in nondecreasing order of their isothetic distances from
$\rp{s,t}$.
This is needed to maintain locally minimum isothetic distance from $\rp{s,t}$
while running PrioritizedBFS.
To maintain the global minimum isothetic distance from $\rp{s,t}$ throughout the
path $\gp{l}{m,n}{s,t}$, we use dynamic programming.
We keep track of a variable $\delta(p,\gp{l}{m,n}{s,t})$ associated with each voxel $p$
in the traversed set, using the following recurrence.
\[
\delta\left(p,\gp{l}{m,n}{s,t}\right) = \left\{
\begin{array}{l@{}l}
0 & \mbox{if $p=s$}\\
\max\bigg(\id\left(p,\rp{s,t}\right),\min
\limits_{q\in \vadj{l}{p}}\left
\{\delta \left( q,\gp{l}{m,n}{s,t} \right)\right\}\bigg)& \mbox{otherwise}
\end{array}\right.
\]
where $\vadj{l}{p}$ denotes the set of $l$neighbors of $p$ that have been
visited by the algorithm on reaching $p$. Figure on left: Discrete spherical geodesics and their corresponding circles for $r=30$, class NS, $l=1$. The sequence of red voxels is $\gp{1}{1,2}{s,t}$ with $s(8,25,14)\in\qoct{6}$ and $t(29,3,6)\in\qoct{3}$, which, when combined with $\gp{1}{1,2}{t,s}$, shown in yellow, yields the discrete 3D geodesic circle passing through $s$, $t$, and centered at $o$. Shown in blue are 16 longitude circles produced by extending the geodesics from source points taken from the discrete great circle on $zx$plane to destination point $t(0,30,0)$ for each. 