Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
From MaRDI portal
Publication:1097884
DOI10.1007/BF02579170zbMath0636.05003OpenAlexW2019176509WikidataQ56457309 ScholiaQ56457309MaRDI QIDQ1097884
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579170
Related Items
A simplified technique for hidden-line elimination in terrains ⋮ Finding cores of limited length ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING ⋮ On approximate range counting and depth ⋮ The maximum absolute deviation measure in location problems on networks ⋮ Unnamed Item ⋮ Extremal polygon containment problems ⋮ Selecting distances in the plane ⋮ A reduction of lattice tiling by translates of a cubical cluster ⋮ 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 ⋮ An efficient algorithm for hidden surface removal. II ⋮ Generalized Davenport-Schinzel sequences ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ Almost fully-parallel parentheses matching ⋮ On minimum and maximum spanning trees of linearly moving points ⋮ Arrangements of segments that share endpoints: Single face results ⋮ Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram ⋮ An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems ⋮ Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity ⋮ A linear-time heuristic for minimum rectangular coverings (Extended abstract) ⋮ Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric ⋮ Convex polygons made from few lines and convex decompositions of polyhedra ⋮ Computing depth orders and related problems ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Almost linear upper bounds on the length of general Davenport-Schinzel sequences ⋮ Planar realizations of nonlinear Davenport-Schinzel sequences by segments ⋮ On the two-dimensional Davenport-Schinzel problem ⋮ Triangles in space or building (and analyzing) castles in the air ⋮ Coordinated motion planning for two independent robots ⋮ Combinatorial aspects of Davenport-Schinzel sequences ⋮ Separating two simple polygons by a sequence of translations ⋮ 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 ⋮ Finite sphere packing and sphere covering ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Extremal functions for sequences ⋮ Improved lower bounds on the length of Davenport-Schinzel sequences ⋮ Computing depth orders for fat objects and related problems ⋮ Generalized hidden surface removal ⋮ A simplified construction of nonlinear Davenport-Schinzel sequences ⋮ A survey of motion planning and related geometric algorithms ⋮ Compaction and separation algorithms for non-convex polygons and their applications ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Combinatorial complexity of translating a box in polyhedral 3-space ⋮ Enumerating Davenport-Schinzel sequences ⋮ On the boundary of a union of Rays ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Turán problems for edge-ordered graphs ⋮ Remarks on the computation of the horizon of a digital terrain ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Common intersections of polygons ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ An optimal algorithm for the boundary of a cell in a union of rays ⋮ Efficient binary space partitions for hidden-surface removal and solid modeling ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences ⋮ The upper envelope of piecewise linear functions: Tight bounds on the number of faces ⋮ The upper envelope of piecewise linear functions: Algorithms and applications ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Finding the conditional location of a median path on a tree ⋮ 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 ⋮ On critical orientations in the Kedem-Sharir motion planning algorithm ⋮ On the number of maximum empty boxes amidst \(n\) points ⋮ On the deque conjecture for the splay algorithm ⋮ An iterated local search algorithm for the time-dependent vehicle routing problem with time windows ⋮ 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 ⋮ Upper envelope onion peeling ⋮ Voronoi diagrams of rigidly moving sets of points ⋮ Generalized Davenport-Schinzel sequences with linear upper bound ⋮ Minimum-link paths among obstacles in the plane ⋮ The upper envelope of Voronoi surfaces and its applications ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ Dynamic computational geometry on meshes and hypercubes ⋮ Upper envelope onion peeling ⋮ Finding the upper envelope of n line segments in O(n log n) time ⋮ The complexity and construction of many faces in arrangements of lines and of segments ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Penny-packing and two-dimensional codes ⋮ On arrangements of Jordan arcs with three intersections per pair ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 ⋮ On determining optimal strategies in pursuit games in the plane ⋮ Optimal output-sensitive convex hull algorithms in two and three dimensions ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces ⋮ On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space ⋮ 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 ⋮ On the union of fat wedges and separating a collection of segments by a line ⋮ Weak visibility queries of line segments in simple polygons ⋮ Testing string superprimitivity in parallel ⋮ The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis ⋮ Voronoi Diagrams of Moving Points ⋮ Visibility with a moving point of view
Cites Work
- Unnamed Item
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Rapidly growing Ramsey functions
- Efficiency of a Good But Not Linear Set Union Algorithm
- A Combinatorial Problem Connected with Differential Equations
- Some properties of Davenport-Schinzel sequences
- A combinatorial problem connected with differential equations II
- On the interpretation of non-finitist proofs–Part II
