Two general methods for dynamizing decomposable searching problems

We define two classes of decomposable searching problems and consider ways of efficiently dynamizing them. For the first class, DD, we show that both insertions and deletions can be processed efficiently. For the second class, MD, we exploit a merge technique to obtain better insertion times. We also give a number of examples of problems to which the methods apply, including the dynamic maintenance of quadtrees and of the common intersection of finitely many halfspaces in the plane.