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.05003OpenAlexW1998230386WikidataQ56545274 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
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, 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, 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
