The upper envelope of piecewise linear functions: Algorithms and applications (Q919830)

This article is devoted to the combinatorial complexity of the upper envelope of piecewise linear functions and its consequences to various problems in computational geometry. The upper envelope of the system of functions is defined as its pointwise maximum. In the case of linear functions the envelope form a cell complex. The complexity of the complex is the number of its faces. An algorithm is presented for finding the upper envelope of n linear functions defined in the space \(R^ 3\). The algorithm is asymptotically optimal and its time complexity is \(O(n^ 2\alpha (n))\) where \(\alpha\) (n) is the inverse of Ackermann's function. Finding an upper envelope for appropriate system of linear functions solves a number of problems of computational geometry. Among the applications are mentioned problems of hidden line and surface removal, translating a polyhedron in the space with polyhedral obstacles, finding Voronoi diagrams of point clusters.