Lower Envelopes of Surface Patches in 3-Space

Let Σ be a collection of n surface patches, each being the graph of a partially defined semi-algebraic function of constant description complexity, and assume that any triple of them intersect in at most s = 2 points. We show that the complexity of the lower envelope of the surfaces in Σ is O(n2 log6+ε n), for any ε > 0. This almost settles a long-standing open problem posed by Halperin and Sharir [26], thirty years ago, who showed the nearly-optimal albeit weaker bound of O(n2 · 2c√log n) on the complexity of the lower envelope, where c > 0 is some constant. Our approach is fairly simple and is based on hierarchical cuttings and gradations, as well as a simple charging scheme. We extend our analysis to the case s > 2, under a “favorable cross section” assumption, in which case we show that the bound on the complexity of the lower envelope is O(n2 log11+ε n), for any ε > 0. Incorporating these bounds with the randomized incremental construction algorithms of Boissonnat and Dobrindt [16], we obtain efficient constructions of lower envelopes of surface patches with the above properties, whose overall expected running time is O(n2polylogn), as well as efficient data structures that support point location queries in their minimization diagrams in O(log2 n) expected time.

Duke Scholars

Author Pankaj K. Agarwal Computer Science