The overlay of lower envelopes and its applications

Let and be two collections of a total ofn (possibly partially defined) bivariate, algebraic functions of constant maximum degree. The minimization diagrams of are the planar maps obtained by the xy-projections of the lower envelopes of , respectively. We show that the combinatiorial complexity of the overlay of the minimization diagrams of and of is O(n^2+ɛ), for any ɛ>0. This result has several applications: (i) a near-quadratic upper bound on the complexity of the region in 3-space enclosed between the lower envelope of one such collection of functions and the upper envelope of another collection; (ii) an efficient and simple divide-and-conquer algorithm for constructing lower envelopes in three dimensions; and (iii) a near-quadratic upper bound on the complexity of the space of all plane transversals of a collection of simply shaped convex sets in three dimensions. Work on this paper by the first author was supported by National Science Foundation Grant CCR-93-01259 and an NYI award. Work on this paper by the second author was supported by the Netherlands’ Organization for Scientific Research (NWO) and partially supported by ESPRIT Basic Research Action No. 6546 (project PROMotion). His current address is Department of Computer Science, Postech, San 31, Hyoja-Dong, Pohang, Kyungbuk 790–784, South Korea. Email: otfried@vision.postech.ac.kr. Work on this paper by the third author was supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.