Dynamization of order decomposable set problems

Order decomposable set problems are introduced as a general class of problems concerning sets of multidimensional objects. We give a method of structuring sets such that the answer to an order decomposable set problem can be maintained with low worst-case time bounds, while objects are inserted and deleted in the set. Examples include the maintenance of the two-dimensional Voronoi diagram of a set of points, and of the convex hull of a three-dimensional point set in linear time. We show that there is a strong connection between the general dynamization method given and the well-known technique of divide-and-conquer used for solving many problems concerning static sets of objects. Although the upper bounds obtained are low in order of magnitude, the results do not necessarily imply the existence of fast feasible update routines. Hence the results merely assess theoretical bounds for the various set problems considered.