The upper envelope of piecewise linear functions: Tight bounds on the number of faces

DOI10.1007/BF02187734zbMath0707.68043MaRDI QIDQ919829

Herbert Edelsbrunner

Publication date: 1989

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

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

zbMATH Keywords

combinatorial complexityenvelopepiecewise linear functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Vertical decompositions for triangles in 3-space, Remarks on the computation of the horizon of a digital terrain, The upper envelope of piecewise linear functions: Algorithms and applications, Quasi-optimal upper bounds for simplex range searching and new zone theorems, The complexity of many cells in arrangements of planes and related problems, On overlays and minimization diagrams, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Cites Work

• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• The upper envelope of piecewise linear functions: Algorithms and applications
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Unnamed Item
• Unnamed Item
• Unnamed Item