The upper envelope of piecewise linear functions: Algorithms and applications
Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. 4(1), 311–336.
Download (ext.)
Journal Article
| Published
| English
Author
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Sharir, Micha
;
Guibas, Leonidas;
Sharir, MichaAbstract
This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper.
Publishing Year
Date Published
1989-12-01
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Acknowledgement
Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from NCRD, the Israeli National Council for Research and Development.
Volume
4
Issue
1
Page
311 - 336
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. 1989;4(1):311-336. doi:10.1007/BF02187733
Edelsbrunner, H., Guibas, L., & Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187733
Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187733.
H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 311–336, 1989.
Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. 4(1), 311–336.
Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:10.1007/BF02187733.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar