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