Almost linear upper bounds on the length of general Davenport-Schinzel sequences
From MaRDI portal
Publication:1097885
DOI10.1007/BF02579209zbMath0636.05004OpenAlexW2077909149MaRDI QIDQ1097885
Publication date: 1987
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579209
Related Items
A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\), A linear upper bound in extremal theory of sequences, Generalized Davenport-Schinzel sequences, Three Generalizations of Davenport--Schinzel Sequences, Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, On the two-dimensional Davenport-Schinzel problem, Extremal functions for sequences, Improved lower bounds on the length of Davenport-Schinzel sequences, A simplified construction of nonlinear Davenport-Schinzel sequences, A survey of motion planning and related geometric algorithms, Enumerating Davenport-Schinzel sequences, Common intersections of polygons, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Davenport-Schinzel theory of matrices, Generalized Davenport-Schinzel sequences with linear upper bound, Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts, Dynamic computational geometry on meshes and hypercubes, On arrangements of Jordan arcs with three intersections per pair, An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, An Output-Sensitive Convex Hull Algorithm for Planar Objects, Visibility with a moving point of view
Cites Work
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Efficiency of a Good But Not Linear Set Union Algorithm
- A Combinatorial Problem Connected with Differential Equations
- Some properties of Davenport-Schinzel sequences
- A combinatorial problem connected with differential equations II
