Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
From MaRDI portal
Publication:911595
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
- A Combinatorial Problem Connected with Differential Equations
- A combinatorial problem connected with differential equations II
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
- Improved lower bounds on the length of Davenport-Schinzel sequences
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On a problem of Davenport and Schinzel
- On the general motion-planning problem with two degrees of freedom
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- On the shortest paths between two convex polyhedra
- On the two-dimensional Davenport-Schinzel problem
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Separating two simple polygons by a sequence of translations
- Some dynamic computational geometry problems
- Some properties of Davenport-Schinzel sequences
- The complexity and construction of many faces in arrangements of lines and of segments
- 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
Cited in
(69)- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity
- Three generalizations of Davenport-Schinzel sequences
- On determining optimal strategies in pursuit games in the plane
- Extremal problems for colored trees and Davenport-Schinzel sequences
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- The overlay of lower envelopes and its applications
- The union of moving polygonal pseudodiscs -- combinatorial bounds and applications
- scientific article; zbMATH DE number 7053339 (Why is no real title available?)
- Robot motion planning and the single cell problem in arrangements
- Combinatorial aspects of Davenport-Schinzel sequences
- Vertical decompositions for triangles in 3-space
- Voronoi Diagrams of Moving Points
- Extremal polygon containment problems
- PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS
- A simplified construction of nonlinear Davenport-Schinzel sequences
- Improved lower bounds on the length of Davenport-Schinzel sequences
- Finding effective ``Force targets for two-dimensional, multifinger frictional grips
- Approximate matching of polygonal shapes
- Enumerating Davenport-Schinzel sequences
- Voronoi diagrams of moving points in higher dimensional spaces
- Bounding sequence extremal functions with formations
- Extremal functions for sequences
- Near-quadratic bounds for the \(L_ 1\) Voronoi diagram of moving points
- On critical orientations in the Kedem-Sharir motion planning algorithm
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Constructing sparse Davenport-Schinzel sequences
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Davenport-Schinzel theory of matrices
- A convex polygon among polygonal obstacle: Placement and high-clearance motion
- Almost tight upper bounds for the single cell and zone problems in the three dimensions
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- A linear upper bound in extremal theory of sequences
- On numbers of Davenport-Schinzel sequences
- Almost tight upper bounds for lower envelopes in higher dimensions
- scientific article; zbMATH DE number 1424289 (Why is no real title available?)
- Generalized Davenport-Schinzel sequences
- On determining optimal strategies in pursuit games in the plane
- Finding the upper envelope of n line segments in O(n log n) time
- Sharp bounds on Davenport-Schinzel sequences of every order
- Voronoi diagrams of rigidly moving sets of points
- On minimum and maximum spanning trees of linearly moving points
- scientific article; zbMATH DE number 1808181 (Why is no real title available?)
- On the number of maximum empty boxes amidst \(n\) points
- Sharp bounds on Davenport-Schinzel sequences of every order
- Efficient on-line algorithms for Euler diagram region computation
- scientific article; zbMATH DE number 1341912 (Why is no real title available?)
- Combinatorial complexity bounds for arrangements of curves and spheres
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- Untangling planar graphs from a specified vertex position-Hard cases
- On \(k\)-sets in arrangements of curves and surfaces
- On the general motion-planning problem with two degrees of freedom
- A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder
- Coordinated motion planning for two independent robots
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Computing half-plane and strip discrepancy of planar point sets
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- scientific article; zbMATH DE number 7673608 (Why is no real title available?)
- A relationship between generalized Davenport-Schinzel sequences and interval chains
- Interview with Micha Sharir
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)
