$ \newcommand{\zzz} {{\mathbb{Z}}^3} \newcommand{\ds} {S_r^{\mathbb{Z}}} % digital sphere \newcommand{\qoct}[1] {{\mathbb{Q}}_{#1}} % q-octant \newcommand{\gp}[1] {{{\pi}}_r^{\mathbb{Z}}(#1)} % geodesic path in \zzz \newcommand{\rp}[1] {{\Pi}_r^{\mathbb{R}}(#1)} % real plane \newcommand{\scp}[1] {{\Pi}_r^{\mathbb{Z}}(#1)} % supercover of \rp \newcommand{\dsrp}[1] {I_r^{\mathbb{Z}}(#1)} % \ds intersection \rp $

Spherical Geodesics in $\zzz$

By a linear-time elementary number-theoretic algorithm
CAUTION! This webpage has SVG images and your browser does not support it.

Algorithm

Ranita Biswas and Partha Bhowmick,
On Finding Spherical Geodesic Paths and Circles in ℤ3,
18th IAPR International Conference on Discrete Geometry for Computer Imagery: DGCI'14, 10-12 September 2014, Siena, Italy,
LNCS 8668, pp. 396-409, Springer.

Contribution

A discrete spherical geodesic path $\gp{s,t}$ between two 3D integer points (voxels) $s$ and $t$ lying on a discrete sphere $\ds$ is a/the 1-connected shortest path from $s$ to $t$, comprising voxels of $\ds$ intersected by the real plane $\rp{s,t}$ passing through $s$, $t$, and the center of $\ds$. We show that $\dsrp{s,t}$, the set of voxels of $\ds$ intersected by $\rp{s,t}$, always contains a 1-connected cycle passing through $s$ and $t$, and each voxel in $\dsrp{s,t}$ lies within an isothetic distance of $\frac32$ from $\rp{s,t}$. Hence, to obtain $\gp{s,t}$, the algorithm starts Prioritized-BFS from $s$, and iteratively computes in constant time each voxel $p$ of $\gp{s,t}$ in succession from the predecessor of $p$.

A novel number-theoretic property is used to facilitate the process of searching the 1-connected voxels comprising $\gp{s,t}$. In addition, the 48-symmetry of discrete sphere is used to decide the quadraginta octants that $\gp{s,t}$ would pass through. The proposed algorithm requires only the radius $r$ of $\ds$ as input, apart from $s$ and $t$. The algorithm is output-sensitive, having its time and space complexities both linear in the length of $\gp{s,t}$.

It can be extended for constructing 1-connected discrete 3D circles of arbitrary orientations, specified by a few appropriate input parameters. Experimental results and some related analysis demonstrate the efficiency and versatility of the proposed technique.

 gp-r30-all.png
Figure: Discrete spherical geodesics and their corresponding circles for $r=30$. The sequence of red voxels is $\gp{s,t}$ with $s=(8,25,14)\in\qoct{6}$ and $t=(29,3,6)\in\qoct{3}$, which, when combined with $\gp{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.