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

DOI10.1007/BF02187734MaRDI QIDQ919829zbMATH OpenFDO

Authors 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

piecewise linear functionsenvelopecombinatorial complexity

Mathematics Subject Classification ID

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

Recommendations

• 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
• Almost tight upper bounds for lower envelopes in higher dimensions
• Upper envelope onion peeling
• Finding the upper envelope of n line segments in O(n log n) time

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• scientific article; zbMATH DE number 3272188 (Why is no real title available?)
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• 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

Cited in

(12)

• Remarks on the computation of the horizon of a digital terrain
• The complexity of many cells in arrangements of planes and related problems
• On overlays and minimization diagrams
• Vertical decompositions for triangles in 3-space
• A new technique for analyzing substructures in arrangements of piecewise linear surfaces
• Finding the upper envelope of n line segments in O(n log n) time
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• The upper envelope of piecewise linear functions: Algorithms and applications
• Almost tight upper bounds for lower envelopes in higher dimensions
• On the two-dimensional Davenport-Schinzel problem
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

This page was built for publication: The upper envelope of piecewise linear functions: Tight bounds on the number of faces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q919829)