Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Explore this paper's citation graph
Summary
This work effectively closes the problem of bounding the complexity of the lower envelope of n univariate functions by establishing sharp bounds on Davenport-Schinzel sequences of every order s by revealing that, contrary to one's intuition, λs(n) behaves essentially like λ s-1( n) when s is odd.
- Type
- article
- Published
- 2012-04-04
- Cited by
- 29
- References
- 100
- Access
- Open access
- OpenAlex
- https://openalex.org/W2570341361
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:6880266
Keywords
Mathematics, Combinatorics, Bounding overwatch, Sequence (biology), Order (exchange)
References
- Efficiency of a Good But Not Linear Set Union Algorithm
- The Complexity of the Union of (alpha, beta)-Covered Objects
- Discrete and Computational Geometry: Papers from the DIMACS Special Year
- Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams
- On a problem of Davenport and Schinzel
- Almost tight upper bounds for vertical decompositions in four dimensions
- A combinatorial problem connected with differential equations II
- Convex hull of points lying on lines in time after preprocessing
- Complexity of a Single Face in an Arrangement of s-Intersecting Curves
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- Planar realizations of nonlinear davenport-schinzel sequences by segments
- On the lower envelope of bivariate functions and its applications
- Space-time tradeoff for answering range queries (Extended Abstract)
- Precise global collision detection in multi-axis NC-machining
- Superlinear Bounds for Matrix Searching Problems
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Generalized Davenport-Schinzel sequences with linear upper bound
- Skewed projections with an application to line stabbing in R3
- Generalized Davenport-Schinzel sequences
- Visibility maps of segments and triangles in 3D
Cited by
- On the zone of a circle in an arrangement of lines
- How To Place a Point to Maximize Angles
- A Relationship Between Generalized Davenport-Schinzel Sequences and Interval Chains
- Kinetic k-Semi-Yao Graph and its Applications
- A simple, faster method for kinetic proximity problems
- On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams
- On the Complexity of Randomly Weighted Voronoi Diagrams
- Three Generalizations of Davenport-Schinzel Sequences
- Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices
- Forbidden formations in 0-1 matrices
- Constructing sparse Davenport-Schinzel sequences by hypergraph edge coloring
- Disjoint edges in topological graphs and the tangled-thrackle conjecture
- Constructing sparse Davenport-Schinzel sequences
- Formations and generalized Davenport-Schinzel sequences
- An algorithm for bounding extremal functions of forbidden sequences
- On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
- Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
- Sequence saturation
- A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices
- Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function
Related papers
- Bounding superposed on-off sources - variability ordering and majorization to the rescue
- Parametric analysis of linear programs with upper bounded variables
- Upper and lower bounds for non-linear composite behaviour
- New lower bounds on the error probability of a given block code
- An upper bound for finite-horizon H/sub 2/ performance of uncertain systems
- Lower bounding techniques for the multiprocessor scheduling problem with communication delay
- THE POWER OF UPPER AND LOWER BOUNDING FUNCTIONS IN BRANCH-AND-BOUND ALGORITHMS
- Efficient Portfolios Computed via Moment-Based Bounding-approximations: Part II - DBFS