The upper envelope of piecewise linear functions: Algorithms and applications

H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 4 (1989) 311–336.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
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
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
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, 4(1), 311–336. 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 4, no. 1 (1989): 311–36. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar