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.