TY - JOUR AB - 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. AU - Edelsbrunner, Herbert AU - Guibas, Leonidas AU - Sharir, Micha ID - 4081 IS - 1 JF - Discrete & Computational Geometry SN - 0179-5376 TI - The upper envelope of piecewise linear functions: Algorithms and applications VL - 4 ER -