article published yes Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 Leonidas Guibas author Micha Sharir author 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. Springer1989 eng 0179-5376 1432-044410.1007/BF02187733 41311 - 336 yes H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 4 (1989) 311–336. Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a> Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):311-336. doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a> H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989. Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a>. Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a>. Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete &#38; Computational Geometry. 4(1), 311–336. 40812018-12-11T12:06:50Z2022-02-10T15:53:48Z