Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
From MaRDI portal
Publication:911595
DOI10.1016/0097-3165(89)90032-0zbMATH Open0697.05003DBLPjournals/jct/AgarwalSS89OpenAlexW1998230386WikidataQ56545274 ScholiaQ56545274MaRDI QIDQ911595FDOQ911595
Authors: Pankaj K. Agarwal, Micha Sharir, Peter W. Shor 
Publication date: 1989
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(89)90032-0
Recommendations
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Sharp bounds on Davenport-Schinzel sequences of every order
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Sharp bounds on Davenport-Schinzel sequences of every order
Cites Work
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- On the general motion-planning problem with two degrees of freedom
- On the two-dimensional Davenport-Schinzel problem
- The complexity and construction of many faces in arrangements of lines and of segments
- Some dynamic computational geometry problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- A Combinatorial Problem Connected with Differential Equations
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Improved lower bounds on the length of Davenport-Schinzel sequences
- On a problem of Davenport and Schinzel
- Separating two simple polygons by a sequence of translations
- Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- On the shortest paths between two convex polyhedra
- Some properties of Davenport-Schinzel sequences
- A combinatorial problem connected with differential equations II
Cited In (66)
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Extremal problems for colored trees and Davenport-Schinzel sequences
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Title not available (Why is that?)
- Untangling planar graphs from a specified vertex position-Hard cases
- Bounding sequence extremal functions with formations
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Voronoi diagrams of rigidly moving sets of points
- Coordinated motion planning for two independent robots
- Extremal polygon containment problems
- Finding effective ``Force targets for two-dimensional, multifinger frictional grips
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Efficient on-line algorithms for Euler diagram region computation
- On the number of maximum empty boxes amidst \(n\) points
- Title not available (Why is that?)
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- A simplified construction of nonlinear Davenport-Schinzel sequences
- Improved lower bounds on the length of Davenport-Schinzel sequences
- Combinatorial complexity bounds for arrangements of curves and spheres
- A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Vertical decompositions for triangles in 3-space
- A linear upper bound in extremal theory of sequences
- Title not available (Why is that?)
- Generalized Davenport-Schinzel sequences
- The union of moving polygonal pseudodiscs -- combinatorial bounds and applications
- Voronoi Diagrams of Moving Points
- Enumerating Davenport-Schinzel sequences
- Constructing sparse Davenport-Schinzel sequences
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Three Generalizations of Davenport--Schinzel Sequences
- Combinatorial aspects of Davenport-Schinzel sequences
- Davenport-Schinzel theory of matrices
- Extremal functions for sequences
- On the general motion-planning problem with two degrees of freedom
- On determining optimal strategies in pursuit games in the plane
- Finding the upper envelope of n line segments in O(n log n) time
- Title not available (Why is that?)
- Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- The overlay of lower envelopes and its applications
- Approximate matching of polygonal shapes
- On \(k\)-sets in arrangements of curves and surfaces
- On determining optimal strategies in pursuit games in the plane
- On minimum and maximum spanning trees of linearly moving points
- Almost tight upper bounds for lower envelopes in higher dimensions
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- Robot motion planning and the single cell problem in arrangements
- PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS
- Voronoi diagrams of moving points in higher dimensional spaces
- On numbers of Davenport-Schinzel sequences
- Almost tight upper bounds for the single cell and zone problems in the three dimensions
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Near-quadratic bounds for the \(L_ 1\) Voronoi diagram of moving points
- On critical orientations in the Kedem-Sharir motion planning algorithm
- A convex polygon among polygonal obstacle: Placement and high-clearance motion
- Title not available (Why is that?)
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- Computing half-plane and strip discrepancy of planar point sets
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- Interview with Micha Sharir
- A relationship between generalized Davenport-Schinzel sequences and interval chains
This page was built for publication: Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911595)
