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

DOI10.1007/BF02187734zbMATH Open0707.68043MaRDI QIDQ919829FDOQ919829

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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: Algorithms and applications
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

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)