On the two-dimensional Davenport-Schinzel problem

DOI10.1016/S0747-7171(08)80070-3zbMath0717.68050OpenAlexW4213019905MaRDI QIDQ2638785

Jacob T. Schwartz, Micha Sharir

Publication date: 1990

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0747-7171(08)80070-3

zbMATH Keywords

upper boundslower boundsDavenport-Schinzel problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Castles in the air revisited, On non-smooth convex distance functions, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Almost tight upper bounds for lower envelopes in higher dimensions, Constructing the minimization diagram of a two-parameter problem, Almost tight upper bounds for the single cell and zone problems in the three dimensions, An algorithm for constructing the convex hull of a set of spheres in dimension \(d\), A survey of motion planning and related geometric algorithms, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, On \(k\)-sets in arrangements of curves and surfaces, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, Robot motion planning and the single cell problem in arrangements, Voronoi Diagrams for Parallel Halflines and Line Segments in Space, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Cites Work

• Unnamed Item
• 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
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Voronoi diagrams and arrangements
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Fractional cascading. I: A data structuring technique
• Improved lower bounds on the length of Davenport-Schinzel sequences
• Voronoi diagrams from convex hulls
• On the number of line separations of a finite set in the plane
• On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• Searching and storing similar lists
• On a problem of Davenport and Schinzel
• Convex hulls of finite sets of points in two and three dimensions
• A Combinatorial Problem Connected with Differential Equations
• A combinatorial problem connected with differential equations II