Hyperspheres in digital geometry (Q909499)

For two points x,y of the k-dimensional rectangular grid, their distance may be defined as \[ d_ m(x,y)=\max \{L_{\infty}(x,y),\frac{1}{m}L_ 1(x,y)\}, \] where \(L_ p\) denotes the standard \(L_ p\)-norm in k- space. The volume (or surface) of a digitized k-dimensional sphere with radius r around grid point x is measured by the number of grid points y satisfying \(d_ m(x,y)\leq r\) \((or=r)\). Thus the volume just equals the sum of the volumes of unit hypercubes centered at these grid points y. The authors obtain polynomials in r of degree k (or k-1) describing the volume (surface) of a digitized sphere. They also outline a construction for obtaining the (rational) coefficients of these polynomials, but give no concrete complexity analysis. Further, they show that the relative volumetric (surface) error with respect to Euclidean spheres is bounded, for arbitrary dimensions k and choices of the `weighting parameter' m.