Off-line maintenance of planar configurations

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 set, 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 preprocess a sequence of n insertions and deletions in O(n log n) time and space, 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 structures, 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 open problem in computational geometry. (C) 1996 Academic Press, Inc.