We achieve an O(log n) amortized time bound per operation for the off-
line version of the dynamic convex hull problem in the plane. In this
problem, a sequence of n insert, delete, and query instructions are to
be processed, where each insert instruction adds a new point to the s
et, each delete instruction removes an existing point, and each query
requests a standard convex hull search. We process the entire sequence
in total O(n log n) time and O(n) space. Alternatively, we can prepro
cess a sequence of n insertions and deletions in O(n log n) time and s
pace, then answer queries in history in O(log n) time apiece (a query
in history means a query comes with a time parameter t, and it must be
answered with respect to the convex hull present at time t). The same
bounds also hold for the off-line maintenance of several related stru
ctures, such as the maximal vectors, the intersection of half-planes,
and the kernel of a polygon. Achieving an O(log n) per-operation time
bound for the on-line versions of these problems is a longstanding ope
n problem in computational geometry. (C) 1996 Academic Press, Inc.