$ \newcommand{\zzz} {{\mathbb{Z}}^3} \newcommand{\ds} {S_r^{\mathbb{Z}}} % digital sphere \newcommand{\qoct}[1] {{\mathbb{Q}}_{#1}} % q-octant \newcommand{\gp}[3] {{{\pi}}_{#2}^{(#1)}(#3)} % geodesic path in \zzz \newcommand{\rp}[1] {{\Pi}^{\mathbb{R}}(#1)} % real plane \newcommand{\dsrp}[2] {I_{#1}^{\mathbb{Z}}(#2)} % \ds intersection \rp \newcommand{\scp}[1] {{\Pi}_r^{\mathbb{Z}}(#1)} % supercover of \rp \newcommand{\id} {d_{\perp}} \newcommand{\adj}[2] {\mathbb A^{(#1)}(#2)} % l-adjacent voxels of #1 \newcommand{\vadj}[2] {\mathbb B^{(#1)}(#2)} % visited l-adjacent voxels of #1 $

Topology of Spherical Geodesics in $\zzz$

Different classes and their characterization
CAUTION! This webpage has SVG images and your browser does not support it.


Ranita 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.


A 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 naive-naive (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 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 is output-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.

gp-r30-all.png 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 Prioritized-BFS 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 non-decreasing order of their isothetic distances from $\rp{s,t}$. This is needed to maintain locally minimum isothetic distance from $\rp{s,t}$ while running Prioritized-BFS. 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.