Institute for Mathematical Sciences

Preprint ims14-04

R. Adler, T. Nowicki, G. Swirszcz, C. Tresser, S. Winograd
Error Diffusion on Simplices: Invariant Regions, Tessellations and Acuteness

Abstract: The error diffusion algorithm can be considered as a time dependent dynamical system that transforms a sequence of inputs into a sequence of inputs. That dynamical system is a time dependent translation acting on a partition of the phase space Aff, a finite dimensional real affine space, into the Voronoi regions of the set C of vertices of some polytope Pol where the inputs all belong.

Given a sequence inp(i) of inputs that are point in Aff, inp(i) gets added to the error vector e(i), the total vector accumulated so far, that belongs to the (Euclidean) vector space mofelling Aff. The sum inp(i)+e(i) is then again in Aff, thus in a well defined element of the partition of Aff that determines in turns one vertex v(i). The point v(i) of Aff is the i-th output, and the new error vector to be used next is e(i+1)=inp(i)+e(i)-v(i). The maps e(i)->e(i+1) and inp(i)+e(i)->inp(i+1)+e(i+1) are two form of error diffusion, respectively in the vector space and affine space. Long term behavior of the algorithm can be deduced from the asymptotic properties of invariant sets, especially from the absorbing ones that serve as traps to all orbits. The existence of invariant sets for arbitrary sequence of inputs has been established in full generality, but in such a context, the invariant sets that are shown to exist are arbitrarily large and only few examples of minimal invariant sets can be described. Since the case of constant input (that corresponds to a time independent translation) has its own interest, we study here the invariant set for constant input for special polytopes that contain the n-dimensional regular simplices.

In that restricted context of interest in number theory, we study the properties of the minimal absorbing invariant set and prove that typically those sets are bounded fundamental sets for a discrete lattice generated by the simplex and that the intersections of those sets with the elements of the partition are fundamental sets for specific derived lattices.

View ims14-04 (PDF format)