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

H. Edelsbrunner, Discrete & Computational Geometry 4 (1989) 337–343.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
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.
Publishing Year
Date Published
1989-11-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565. Research on the presented result was partially carried out while the author worked for the IBM T. J. Watson Research Cen
Volume
4
Issue
4
Page
337 - 343
IST-REx-ID

Cite this

Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry. 1989;4(4):337-343. doi:10.1007/BF02187734
Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry, 4(4), 337–343. https://doi.org/10.1007/BF02187734
Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” Discrete & Computational Geometry 4, no. 4 (1989): 337–43. https://doi.org/10.1007/BF02187734.
H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight bounds on the number of faces ,” Discrete & Computational Geometry, vol. 4, no. 4, pp. 337–343, 1989.
Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry. 4(4), 337–343.
Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” Discrete & Computational Geometry, vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:10.1007/BF02187734.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar