The upper envelope of piecewise linear functions: Tight bounds on the number of faces - Edelsbrunner, Herbert (Discrete & Computational Geometry, 1989)
This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.
published
yes
yes
Keywords: article