Efficient splitting and merging algorithms for order decomposable problems

Let S be a set whose items are sorted with respect to d > 1 total orders <( 1),..., <(d), and which is subject to dynamic operations, such as insertion s of a single item, deletions of a single item, split and concatenate opera tions performed according to any chosen order <(i) (1 less than or equal to i less than or equal to d). This generalizes to dimension d > 1 the notion of concatenable data structures, such as the 2-3-trees, which support spli ts and concatenates under a single total order. The main contribution of th is paper is a general and novel technique for solving order decomposable pr oblems on S which yields new and efficient concatenable data structures for dimension d > 1. By using our technique we maintain S with the time bounds : O(log n) for the insertion or the deletion of a single item, where n is t he number of items currently in S; n(1 - 1/d) for splits and concatenates a long any order, and for rectangular range queries. The space required is O( n). We provide several applications of our technique. Namely, we present ne w multidimensional data structures implementing two-dimensional priority qu eues, two-dimensional search trees, and concatenable interval trees; these data structures allow us to improve many previously known results on decomp osable problems under split and concatenate operations, such as membership query, minimum-weight item, range query, convex hulls, and Voronoi diagrams . (C) 1999 Academic Press.