Enumerating Davenport-Schinzel sequences

 Access to full text

 Full (PDF)

1. 1. P. AGARWAL, Intersection and decomposition algorithms for arrangements of curves in the plane. Ph. D., New York University, Courant Institute of Mathematical Sciences, 1989. MR2638381
2. 2. P. AGARWAL, M. SHARIR and P. SHOR, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. J. Combinat. Theory Ser. A, 52, (2) : 228-274, 1989. Zbl0697.05003MR1022320
3. 3. P. ALEVIZOS, J. D. BOISSONNAT and F. PREPARATA, An optimal algorithm for the boundary of a cell in a union of rays. Algorithmica, 5, (4) : 573-590, 1990. Zbl0697.68030MR1072808
4. 4. R. COLE and M. SHARIR, Visibility of a polyhedral surface from a point. Technical Report 266, Comp. Science Dept., Courant Institute of Mathematical Sciences, New York University, December 1986. 
5. 5. H. DAVENPORT, A combinatorial problem connected with differential equations II. Acta Arithmetica, XVII : 363-372, 1971. Zbl0216.30204MR285401
6. 6. H. DAVENPORT and A. SCHINZEL, A combinatorial problem connected with differential equations. Amer. J. Math., 87 : 684-694, 1965. Zbl0132.00601MR190010
7. 7. P. FLAJOLET, Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49, (2) : 283-310, 1987. Zbl0612.68069MR909335
8. 8. P. FLAJOLET and A. ODLYZKO, Singularity analysis of generating fonctions. SIAM Journal on Discrete Mathematics, 3, (2) : 216-240, 1990. Zbl0712.05004MR1039294
9. 9. D. GOUYOU-BEAUCHAMPS and B. VAUQUELIN, Deux propriétés combinatoires des nombres of Schröder. Informatique Théorique et Applications, 22, (3) : 361-388, 1988. Zbl0669.05002MR963597
10. 10. S. HART and M. SHARIR, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6 : 151-177, 1986. Zbl0636.05003MR875839
11. 11. K. KEDEM and M. SHARIR, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles. In ACM Symp. on Computational Geometry, pp. 75-8, 1985. 
12. 12. P. KOMJÁTH, A simplified construction of nonlinear Davenport-Schinzel sequences. J. Combin. Theory Ser. A, 49, (2) : 262-267, 1988. Zbl0673.05001MR964387
13. 13. D. LEVEN and M. SHARIR, On the number of critical free contacts of a convex polygonal object moving in 2-dimensional polygonal space. Discrete Comp. Geom., 2 : 255-270, 1987. Zbl0616.52009MR892172
14. 14. J. PACH and M. SHARIR, The upper envelope of a piecewise linear function and the boundary of a region enclosed by convex plates: Combinatorial Analysis. Discrete Comp. Geom., 4, (4) : 291-309, 1989. Zbl0734.05054MR996764
15. 15. R. POLLACK, M. SHARIR and S. SIFRONY, Separating two simple polygons by a sequence of translations. Discrete Comp. Geom., 3 : 123-136, 1988. Zbl0646.68052MR920698
16. 16. M. SHARIR, Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica, 7, (1) : 131-143, 1987. Zbl0636.05004MR905160
17. 17. M. SHARIR, Davenport-Schinzel sequences and their geometric applications, chapter Theoretical Foundations of Computer Graphics and CAD, pp. 253-278. Springer-Verlag, NATO ASI Series, Vol. F-40, R.A. Earnshaw edition, 1988. MR944720
18. 18. M. SHARIR, R. COLE, K. KEDEM, D. LEVEN, R. POLLACK and S. SIFRONY, Geometric applications of Davenport-Schinzel sequences. In 27th Symposium on Foundations of Computer Science, pp.77-86, Toronto (Canada), 1986. 
19. 19. M. SORIA, Méthodes d'analyse pour les constructions combinatoires et les algorithmes. Thèse d'État, L.R.I, Université Paris-Sud (Orsay), Juillet 1990. 
20. 20. E. SZEMERÉDI, On a problem by Davenport and Schinzel. Acta Arithmetica XXV: 213-224, 1974. Zbl0291.05003MR335463
21. 21. A. WIERNIK, Planar realizations of nonlinear Davenport-Schinzel sequences by segments. In 27th Symposium on Foundations of Computer Science, pp.97-106, Toronto (Canada), 1986.