Let F be a collection of n d-variate, possibly partially defined, func
tions, all algebraic of some constant maximum degree. We present a ran
domized algorithm that computes the vertices, edges, and 2-faces of th
e lower envelope (i.e., pointwise minimum) of F in expected time O(n(d
+epsilon)) for any epsilon > 0. For d = 3, by combining this algorithm
with the point-location technique of Preparata and Tamassia, we can c
ompute, in randomized expected time O(n(3+epsilon)), for any epsilon >
0, a data structure of size O(n(3+epsilon)) that, for any query point
q, can determine in O(log(2) n.) time the function(s) of F that attai
n the lower envelope at q. As a consequence, we obtain improved algori
thmic solutions to several problems in computational geometry, includi
ng (a) computing the width of a point set in 3-space, (b) computing th
e ''biggest stick'' in a simple polygon in the plane, and (c) computin
g the smallest-width annulus covering a planar point set. The solution
s to these problems run in randomized expected time O(n(17/11+epsilon)
), for any epsilon > 0, improving previous solutions that run in time
O(n(8/5+epsilon)). We also present data structures for (i) performing
nearest-neighbor and related queries for fairly general collections of
objects in 3-space and for collections of moving objects in the plane
and (ii) performing ray-shooting and related queries among n spheres
or more general objects in 3-space. Both of these data structures requ
ire O(n(3+epsilon)) storage and preprocessing time, for any epsilon >
0, and support polylogarithmic-time queries. These structures improve
previous solutions to these problems.