Suite de Davenport-Schinzel
En combinatoire, une suite de Davenport-Schinzel est une suite de symboles dans laquelle le nombre de fois oĂč deux symboles peuvent apparaĂźtre en alternance est limitĂ©. La longueur d'une suite de Davenport-Schinzel est limitĂ©e par le nombre de ses symboles distincts multipliĂ© par un facteur petit mais non constant qui dĂ©pend du nombre d'alternances qui sont permises. Les suites de Davenport-Schinzel furent dĂ©finies pour la premiĂšre fois par Harold Davenport et Andrzej Schinzel afin d'analyser les Ă©quations diffĂ©rentielles linĂ©aires. Ces sĂ©ries et leurs limitations de longueur sont Ă©galement devenues des outils standard en gĂ©omĂ©trie discrĂšte et dans l'analyse des algorithmes gĂ©omĂ©triques[1].
DĂ©finition
Une suite finie de « symboles » U = u1, u2, u3, ... uN est dite suite de DavenportâSchinzel d'ordre s si elle satisfait aux deux propriĂ©tĂ©s suivantes :
- deux valeurs consĂ©cutives de la suite ne peuvent ĂȘtre Ă©gales.
- si x et y sont deux valeurs distinctes se produisant dans la suite, alors la suite ne contient pas de sous-suite ... x, ... y, ..., x, ..., y, ... consistant en s + 2 valeurs alternant entre x et y mais contient une sous-suite de longueur s + 1 avec deux symboles distincts.
Ainsi, la suite :
- 1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3
est une suite de DavenportâSchinzel d'ordre 3. Elle contient des sous-suites alternatives de longueur quatre, comme ...1, ... 2, ... 1, ... 2, ... (qui apparaĂźt de quatre maniĂšres diffĂ©rentes comme une sous-suite dans la suite globale), mais ne contient aucune sous-suite alternative de longueur cinq.
Si une suite de DavenportâSchinzel d'ordre s comprend n valeurs distinctes, elle est appelĂ©e suite de DavenportâSchinzel (n,s), ou suite DS(n,s)[2].
Limites aux longueurs
La complexité des suites DS(n,s) a été analysée asymptotiquement lorsque n tend vers l'infini, en supposant que s est une constante fixe. Des bornes fortes presque optimales sont connues pour tout s.
Soit λs(n) la longueur de la suite DS(n,s) la plus longue. Les meilleurs limites connues sur λs utilisent la fonction d'Ackermann inverse.
- α(n) = min { m | A(m,m) ℠n },
oĂč A est la fonction d'Ackermann. En raison de la croissance trĂšs rapide de la fonction d'Ackermann, son inverse α croĂźt trĂšs lentement, et est d'au plus quatre pour les problĂšmes de taille pratique[3].
Avec les notations de Landau (o et O), on connait les limites suivantes :
- λ1(n) = n[4],
- λ2(n) = 2n â 1[4].
- [5]. Cette borne de complexitĂ© peut ĂȘtre rĂ©alisĂ©e avec un facteur constant par des segments de droite : il existe des arrangements de n segments de droite dans le plan dont les enveloppes les plus basses ont la complexitĂ© Ω(n α(n))[6].
- pour les valeurs paires de sâ„ 4[7], , oĂč t = s/2 â 1.
- pour les valeurs impaires de sâ„ 5[7], .
La valeur de λs(n) est connue également lorsque s est variable et n une constante petite[8] :
Application aux enveloppes basses
L'enveloppe basse d'un ensemble de fonctions Æi(x) d'une variable rĂ©elle x est la fonction donnĂ©e par leurs minimums en chaque point :
- Æ(x) = mini Æi(x).
On suppose que ces fonctions ont des comportements favorables : elles sont toutes continues, et chaque paire d'entre elles sont Ă©gales en au moins s valeurs. Avec ces hypothĂšses, la droite rĂ©elle peut ĂȘtre dĂ©coupĂ©e en de nombreux intervalles finis dans lesquels une fonction Ă ses valeurs plus basses que celles de toutes les autres. La sĂ©rie de ces intervalles, dĂ©signĂ©e par la fonction de minimisation dans chacun des intervalles, forme une suite de DavenportâSchinzel d'ordre s. Donc, toute limite supĂ©rieure de la complexitĂ© d'une suite de DavenportâSchinzel de cet ordre limite aussi le nombre d'intervalles dans cette reprĂ©sentation de l'enveloppe basse.
Dans l'application originelle de Davenport et Schinzel, les fonctions considĂ©rĂ©es Ă©taient un ensemble de solutions diffĂ©rentes Ă la mĂȘme Ă©quation diffĂ©rentielle linĂ©aire homogĂšne d'ordre s. Toute paire de solutions distinctes peut avoir au plus s valeurs en commun, et donc l'enveloppe basse d'un ensemble de n solutions distinctes forme une suite DS(n,s).
Ce mĂȘme concept d'enveloppe basse peut aussi ĂȘtre appliquĂ© aux fonctions qui sont continues par morceaux ou dĂ©finies seulement sur des intervalles de la droite rĂ©elle. Cependant, dans ce cas, les points de discontinuitĂ©s des fonctions et des extrĂ©mitĂ©s de l'intervalle dans lequel chaque fonnction est dĂ©finie ajoute Ă l'ordre de la suite. Ainsi un segment de droite non vertical dans le plan peut ĂȘtre considĂ©rĂ© comme le graphe d'une fonction liant un intervalle de x valeurs aux valeurs y correspondantes, et l'enveloppe basse d'un ensemble de segments de droite forme une suite de DavenportâSchinzel d'ordre trois car toute paire de segments de droite peut former une sous-suite alternative avec une longueur d'au plus quatre.
Notes et références
Notes
- Atallah 1985 ; Sharir et Agarwal 1995, p. x et 2.
- Voir Sharir et Agarwal 1995, p. 1, pour cette notation.
- Sharir et Agarwal 1995, p. 14
- Sharir et Agarwal 1995, p. 6
- Sharir et Agarwal 1995, chapitre 2, p. 12-42 ; Hart et Sharir 1986 ; Wiernik et Sharir 1988 ; KomjĂĄth 1988 ; Klazar 1999 ; Nivasch 2009.
- Sharir et Agarwal 1995, chapitre 4, p. 86-114 ; Wiernik et Sharir 1988.
- Sharir et Agarwal 1995, chapitre 3, p. 43-85 ; Agarwal, Sharir & Shor 1989; Nivasch 2009.
- Roselle et Stanton 1970/71.
Références
- (en) Cet article est partiellement ou en totalitĂ© issu de lâarticle de WikipĂ©dia en anglais intitulĂ© « DavenportâSchinzel sequence » (voir la liste des auteurs).
- (en) Pankaj K. Agarwal (en), Micha Sharir (en) et P. Shor, « Sharp upper and lower bounds on the length of general DavenportâSchinzel sequences », Journal of Combinatorial Theory, Series A, vol. 52, no 2,â , p. 228â274 (DOI 10.1016/0097-3165(89)90032-0), lien Math Reviews
- (en) Mikhail J. Atallah, « Some dynamic computational geometry problems », Computers and Mathematics with Applications, vol. 11,â , p. 1171â1181 (DOI 10.1016/0898-1221(85)90105-1), lien Math Reviews
- (en) H. Davenport et Andrzej Schinzel, « A combinatorial problem connected with differential equations », American Journal of Mathematics, The Johns Hopkins University Press, vol. 87, no 3,â , p. 684â694 (DOI 10.2307/2373068, lire en ligne), lien Math Reviews
- (en) S. Hart et Micha Sharir, « Nonlinearity of DavenportâSchinzel sequences and of generalized path compression schemes », Combinatorica, vol. 6, no 2,â , p. 151â177 (DOI 10.1007/BF02579170), lien Math Reviews
- (en) M. Klazar, « On the maximum lengths of DavenportâSchinzel sequences », dans Contemporary Trends in Discrete Mathematics, vol. 49, American Mathematical Society, coll. « DIMACS Series in Discrete Mathematics and Theoretical Computer Science », , p. 169â178
- (en) PĂ©ter KomjĂĄth, « A simplified construction of nonlinear DavenportâSchinzel sequences », Journal of Combinatorial Theory, Series A, vol. 49, no 2,â , p. 262â267 (DOI 10.1016/0097-3165(88)90055-6), lien Math Reviews
- (en) R. C. Mullin et R. G. Stanton, « A map-theoretic approach to Davenport-Schinzel sequences. », Pacific Journal of Mathematics, vol. 40,â , p. 167â172 (lire en ligne), lien Math Reviews.
- (en) Gabriel Nivasch, « Improved bounds and new techniques for DavenportâSchinzel sequences and their generalizations », dans Proc. 20th ACM-SIAM Symp. Discrete Algorithms, (lire en ligne), p. 1â10, arXiv:0807.0484
- (en) D. P. Roselle et R. G. Stanton, « Some properties of Davenport-Schinzel sequences », Acta Arithmetica, vol. 17,â 1970/71, p. 355â362, lien Math Reviews.
- (en) Micha Sharir et Pankaj K. Agarwal, DavenportâSchinzel Sequences and Their Geometric Applications, New York, Cambridge University Press, , 1re Ă©d., 372 p. (ISBN 978-0-521-47025-4, LCCN 94030889, lire en ligne).
- (en) R. G. Stanton et P. H. Dirksen, « Davenport-Schinzel sequences. », Ars Combinatoria, vol. 1, no 1,â , p. 43â51, lien Math Reviews.
- (en) R. G. Stanton et D. P. Roselle, « A result on Davenport-Schinzel sequences », dans Combinatorial theory and its applications, III (Proc. Colloq., BalatonfĂŒred, 1969), Amsterdam, North-Holland, , p. 1023â1027, lien Math Reviews.
- (en) Ady Wiernik et Micha Sharir, « Planar realizations of nonlinear DavenportâSchinzel sequences by segments », Discrete & Computational Geometry, vol. 3, no 1,â , p. 15â47 (DOI 10.1007/BF02187894), lien Math Reviews
Voir aussi
Article connexe
Liens externes
- (en) Eric W. Weisstein, « Davenport-Schinzel Sequence », sur MathWorld.
- (en) Davenport-Schinzel Sequences, partie du livre Motion Planning, de Steven M. LaValle.