Planar realizations of nonlinear Davenport-Schinzel sequences by segments

DOI10.1007/BF02187894zbMath0636.68043OpenAlexW1965230032WikidataQ56454445 ScholiaQ56454445MaRDI QIDQ1098294

Publication date: 1988

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131033

zbMATH Keywords

computational geometry inverse Ackermann function Davenport-Schinzel sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Discrete mathematics in relation to computer science (68R99)

Related Items

A linear upper bound in extremal theory of sequences, Generalized Davenport-Schinzel sequences, Three Generalizations of Davenport--Schinzel Sequences, On minimum and maximum spanning trees of linearly moving points, Arrangements of segments that share endpoints: Single face results, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Excess in arrangements of segments, Triangles in space or building (and analyzing) castles in the air, Combinatorial aspects of Davenport-Schinzel sequences, Vertical decompositions for triangles in 3-space, The common exterior of convex polygons in the plane, A simplified construction of nonlinear Davenport-Schinzel sequences, On the boundary of a union of Rays, Combinatorics of intervals in the plane. I: Trapezoids, Drawing graphs using a small number of obstacles, Storing line segments in partition trees, 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, Unions of fat convex polytopes have short skeletons, The upper envelope of piecewise linear functions: Tight bounds on the number of faces, The upper envelope of piecewise linear functions: Algorithms and applications, On the zone of a circle in an arrangement of lines, On the zone of a circle in an arrangement of lines, Straight Skeletons of Three-Dimensional Polyhedra, Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind, On \(k\)-sets in arrangements of curves and surfaces, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Upper envelope onion peeling, The number of edges of many faces in a line segment arrangement, Generalized Davenport-Schinzel sequences with linear upper bound, Upper envelope onion peeling, THE SHUFFLING BUFFER, 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, The maximum absolute deviation measure in location problems on networks, On the general motion-planning problem with two degrees of freedom, On arrangements of Jordan arcs with three intersections per pair, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Energy-optimal routes for battery electric vehicles, Kinetic maintenance of mobile \(k\)-centres on trees, On the complexity of umbra and penumbra, Robot motion planning and the single cell problem in arrangements, On the zone of the boundary of a convex body, On the complexity of a single cell in certain arrangements of surfaces related to motion planning, 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, Visibility with a moving point of view

Cites Work