Solution: We assume the convex hull

to a preprocessing time equal to

just storing points. We assume that this convex hull is stored on a balanced binary

search tree, thus achieving

Now for the algorithm itself. Each vertex of the null defines
a certain interval of slopes

corresponding to those lines supporting the hull at the vertex.
A vertex is completely

characterized by indicating the range of supporting slopes plus whether
it belongs to

the upper or lower hull. (These slopes also correspond to the turning
angle at that vertex.

Since turning angles add up to 360, for each slope *theta* there
are supporting lines with

slope *tan(theta) *at exactly two vertices, one belonging
to the lower and other to the upper

hull.)

By travelling along the upper hull and measuring the turning angles,
we can in *O(n) *time

determine a "upper" partition of the interval [0, Pi] into *n *regions
that correspond each

to the particular range of supporting angles of a vertex in the
upper hull. We

simultaneously define a superimposed "lower" partition corresponding
to the vertices in

the lower hull. We have thus subdivided the interval in at most
*2n* parts, each of

which defines a candidate pair of vertices to determine the width of
the set. We can now

exhaust the possibilites by trying any possible pair. This will
take *O(n)* time.

A few details: To find the width at one of the "candidate pairs"
above, pass a line *l*

connecting the two points and compute among the slopes available for
the pair

(the values contained in the particular subinterval of the subdivision
of [0, Pi] that

correspond to this pair) the one which will give a supporting line
that is as far as possible

from being orthogonal to *l.* The distance between these
two parallel supporting lines

is thus the projection of *l *on the orthogonal direction
to the lines, and was thus minimized

for the pair. These computations take constant time at each pair.

The correctness of the algorithm is guaranteed by the fact that it exhausts
every pair that

may share parallel supporting lines. It does queries in linear
as opposed to

quadratic time because our analysis of the turning angles shows that
there are only
*O(n)* pairs of opposing vertices in a convex polygon, and determines
these possible

pairs in linear time.

Without loss of generality, we may assume the source is at infinity
along the direction

of the *z*-axis. The vertex of *P* with maximum
*x*-coordinate will thus project its shadow

on the *xy*-plane. Call this vertex *v. *Starting
from *v *we procceed to perform a

two-dimensional gift wrapping step (that is, we use the *z*-axis
as hinge) to find the

first edge from *v. *Notice that since *P *is
known, the gift wrapping process runs in time
*O(d(v))*, where *d(v)* is the number of edges incident on
*v.* We continue from the vertex

at the other end of the this edge, and we will finish when we return
back to *v.* The

shadow of *P *is thus the interior and boundary of the convex
polygon traced on the
*xy*-plane by the projections of the edges found in the gift wrapping
process.

The algorithm searches for a point with maximum *x-*coordinate,
which in general could

take time proportional to the number of vertices of *P, *and then
performs one gift

wrapping step for each vertex of *P *that contributes to the shadow.
The running time,

is *O(n(P) + sum(d(v_i)) ),* where the *v_i* are the vertices
of *P *projecting shadow.