Lattice Sphere


Ranita Biswas and Partha Bhowmick,
From Prima Quadraginta Octant to Lattice Sphere through Primitive Integer Operations, Theoretical Computer Science, Vol. 624, pp. 56-72, 2016.


It is the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. It evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences that aids in efficient computation. Each lattice point of the sphere is determined just by a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Theoretical analysis and experimental results demonstrate its simplicity and elegance.