The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
From MaRDI portal
Publication:810525
DOI10.1007/BF02187732zbMath0734.05054OpenAlexW2045561895MaRDI QIDQ810525
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131081
Related Items
Castles in the air revisited, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Almost tight upper bounds for lower envelopes in higher dimensions, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, 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, Almost tight upper bounds for the single cell and zone problems in the three dimensions, On-line construction of the upper envelope of triangles and surface patches in three dimensions, Enumerating Davenport-Schinzel sequences, Sharp upper and lower bounds on the length of general 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, On \(k\)-sets in arrangements of curves and surfaces, Linear approximation of simple objects, Counting facets and incidences, Quasi-optimal upper bounds for simplex range searching and new zone theorems, The upper envelope of Voronoi surfaces and its applications, Unnamed Item, On the general motion-planning problem with two degrees of freedom, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Robot motion planning and the single cell problem in arrangements, On the complexity of a single cell in certain arrangements of surfaces related to motion planning
Cites Work
- Sharp upper and lower bounds on the length of general 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
- Some dynamic computational geometry problems
- 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 arrangements of Jordan arcs with three intersections per pair
- On extremal problems of graphs and generalized graphs
- On the two-dimensional Davenport-Schinzel problem
