preprint-author: 
R. Adler, T. Nowicki, G. Świrszcz, C. Tresser and S. Winograd
preprint-title: 
Error Diffusion on Simplices: Invariant Regions, Tessellations and Acuteness
preprint-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 $\mathbb{A}$, a finite dimensional real affine space, into the Voronoï regions of the set $C$ of vertices of some polytope $\mathbf {P}$ where the inputs all belong.

Given a sequence $g(i)$ of inputs that are point in $\mathbb{A}$, $g(i)$ gets added to the error vector $e(i)$, the total vector accumulated so far, that belongs to the (Euclidean) vector space mofelling $\mathbb{A}$. The sum $g(i)+e(i)$ is then again in $\mathbb{A}$, thus in a well defined element of the partition of $\mathbb{A}$ that determines in turns one vertex $v(i)$. The point $v(i)$ of $\mathbb{A}$ is the $i^\textrm{th}$ output, and the new error vector to be used next is $e(i+1)\,=\, g(i)+e(i)-v(i)$. The maps $e(i)\mapsto e(i+1)$ and $g(i)+e(i)\mapsto g(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.

preprint-year: 
2014