Comptes Rendus
no. 10
Systèmes dynamiques
Dynamique de la diffusion de l'erreur sur plusieurs polytopes

Présenté par : Jean-Christophe Yoccoz

Charles Tresser1
1 IBM, P.O. Box 218, Yorktown Heights, NY 10598, USA
Comptes Rendus. Mathématique, Volume 338 (2004) no. 10, pp. 793-798.

Nous discutons des algorithmes gloutons (pour la norme euclidienne), avec des suites de données dans une famille de polytopes d'un espace affine et les résultats pris parmis les sommets des polytopes respectifs. De tels problèmes d'ordonnancement interviennent dans divers domaines d'applications. Nous produisons quelques exemples simples où l'erreur demeure bornée, même avec une infinité de polytopes. Dans le cas d'un seul polytope, il a été montré par ailleurs, que le caractère borné de l'erreur cumulée est équivalent à l'existence d'une région invariante pour un système dynamique équivalent à l'algorithme et défini dans l'espace affine qui contient ce polytope. Nous montrons, au contraire, qu'il n'existe pas, en général, de région bornée dès que l'on considère au moins deux polytopes différents.

We discuss algorithms for scheduling, greedy for the Euclidean norm, with inputs in a family of polytopes lying in an affine space and the corresponding outputs chosen among the vertices of the respective polytopes. Such scheduling problems arise in various settings. We provide simple examples where the error remains bounded, including cases when there are infinitely many polytopes. In the case of a single polytope the boundedness of the cumulative error is known to be equivalent to the existence of an invariant region for a dynamical system in the affine space that contains this polytope. We show here that, on the contrary, no bounded invariant region can be found in affine space in general, as soon as there are at least two different polytopes.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.01.032
Charles Tresser 1

1 IBM, P.O. Box 218, Yorktown Heights, NY 10598, USA 
@article{CRMATH_2004__338_10_793_0,
     author = {Charles Tresser},
     title = {Dynamique de la diffusion de l'erreur sur plusieurs polytopes},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {793--798},
     publisher = {Elsevier},
     volume = {338},
     number = {10},
     year = {2004},
     doi = {10.1016/j.crma.2004.01.032},
     language = {fr},
}
TY  - JOUR
AU  - Charles Tresser
TI  - Dynamique de la diffusion de l'erreur sur plusieurs polytopes
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 793
EP  - 798
VL  - 338
IS  - 10
PB  - Elsevier
DO  - 10.1016/j.crma.2004.01.032
LA  - fr
ID  - CRMATH_2004__338_10_793_0
ER  - 
%0 Journal Article
%A Charles Tresser
%T Dynamique de la diffusion de l'erreur sur plusieurs polytopes
%J Comptes Rendus. Mathématique
%D 2004
%P 793-798
%V 338
%N 10
%I Elsevier
%R 10.1016/j.crma.2004.01.032
%G fr
%F CRMATH_2004__338_10_793_0
Charles Tresser. Dynamique de la diffusion de l'erreur sur plusieurs polytopes. Comptes Rendus. Mathématique, Volume 338 (2004) no. 10, pp. 793-798. doi : 10.1016/j.crma.2004.01.032. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.01.032/

[1] R. Adler, B. Kitchens, M. Martens, C. Pugh, M. Shub, C. Tresser, Geometric analysis of a greedy algorithm: there exist convex invariant regions (2003) à paraître

[2] R.L. Adler; B.P. Kitchens; M. Martens; C.P. Tresser; C.W. Wu The mathematics of halftoning, IBM J. Res. & Dev., Volume 47 (2003), pp. 1-9

[3] J. Bernoulli Sur une nouvelle espèce de calcul, Recueil Astron. (Berlin), Volume 1 (1772), pp. 255-284

[4] D. Coppersmith, T. Nowicki, G. Paleologo, C. Tresser, C.W. Wu, en préparation

[5] I. Daubechies; R. DeVore Approximating a bandlimited function using very coarsely quantized data: a family of stable sigma-delta modulators of arbitrary order, Ann. of Math., Volume 158 (2003), pp. 643-674

[6] R. Floyd; L. Steinberg An adaptive algorithm for spatial grey scale, SID Symposium Digests of Papers, 1975, pp. 36-37

[7] J.F. Jarvis; C.N. Judice; W.H. Ninke A survey of techniques for the display of continuous tone pictures on bilevel displays, Computer Graphics and Image Processing, Volume 5 (1976), pp. 13-40

[8] M. Keane Interval exchange transformations, Math. Z., Volume 141 (1975), pp. 25-31

[9] M. Martens, T. Nowicki, C. Tresser, C.W. Wu, Convex dynamics: bounds for scheduling, à paraître

[10] M. Morse; G.A. Hedlund Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42

[11] T. Nowicki, C. Tresser, Convex dynamics: unavoidable difficulties in bounding some greedy algorithms, Chaos, à paraître

[12] T. Nowicki, C. Tresser, Convex dynamics: properties of invariant sets, à paraître

[13] A. Schrijver Theory of Linear and Integer Programming, Wiley, Chichester, NY, 1986

[14] R.M. Siegel; C. Tresser; G. Zettler A decoding problem in dynamics and in number theory, Chaos, Volume 2 (1992), p. 473493

[15] J.R. Sullivan, R.L. Miller, T.J. Wetzel, Color digital halftoning with vector error diffusion, US Patent 5070413, 1991

[16] R. Tijdeman The chairman assignment problem, Discrete Math., Volume 32 (1980), pp. 323-330

[17] C.P. Tresser, C.W. Wu, Target patterns controlled error management, US Patent 6101001, 2000

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Refinements and Symmetries of the Morris identity for volumes of flow polytopes

Alejandro H. Morales; William Shi

C. R. Math (2021)

Théorie des hérissons et polytopes

Yves Martinez-Maure

C. R. Math (2003)

Symmetries on plabic graphs and associated polytopes

Xin Fang; Ghislain Fourier

C. R. Math (2018)