--- res: bibo_abstract: - We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).@eng bibo_authorlist: - foaf_Person: foaf_givenName: Herbert foaf_name: Edelsbrunner, Herbert foaf_surname: Edelsbrunner foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-9823-6833 - foaf_Person: foaf_givenName: János foaf_name: Pach, János foaf_surname: Pach - foaf_Person: foaf_givenName: Jacob foaf_name: Schwartz, Jacob foaf_surname: Schwartz - foaf_Person: foaf_givenName: Micha foaf_name: Sharir, Micha foaf_surname: Sharir bibo_doi: 10.1109/SFCS.1987.44 dct_date: 1987^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0272-5428 - http://id.crossref.org/issn/0-8186-0807-2 dct_language: eng dct_publisher: IEEE@ dct_title: On the lower envelope of bivariate functions and its applications@ ...