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 insertions of a single item, deletions of a single item, split and concatenate operations performed according to any chosen order ≺i (1⩽i⩽d). This generalizes to dimension d>1 the notion of concatenable data structures, such as the 2-3-trees, which support splits and concatenates under a single total order. The main contribution of this paper is a general and novel technique for solving order decomposable problems 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 the number of items currently in S; n1−1/d for splits and concatenates along any order, and for rectangular range queries. The space required is O(n). We provide several applications of our technique. Namely, we present new multidimensional data structures implementing two-dimensional priority queues, two-dimensional search trees, and concatenable interval trees; these data structures allow us to improve many previously known results on decomposable problems under split and concatenate operations, such as membership query, minimum-weight item, range query, convex hulls, and Voronoi diagrams.

Efficient splitting and merging algorithms for order decomposable problems / Grossi, R.; Italiano, G. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 154:1(1999), pp. 1-33. [10.1006/inco.1999.2811]

Efficient splitting and merging algorithms for order decomposable problems

ITALIANO G
1999

Abstract

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 insertions of a single item, deletions of a single item, split and concatenate operations performed according to any chosen order ≺i (1⩽i⩽d). This generalizes to dimension d>1 the notion of concatenable data structures, such as the 2-3-trees, which support splits and concatenates under a single total order. The main contribution of this paper is a general and novel technique for solving order decomposable problems 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 the number of items currently in S; n1−1/d for splits and concatenates along any order, and for rectangular range queries. The space required is O(n). We provide several applications of our technique. Namely, we present new multidimensional data structures implementing two-dimensional priority queues, two-dimensional search trees, and concatenable interval trees; these data structures allow us to improve many previously known results on decomposable problems under split and concatenate operations, such as membership query, minimum-weight item, range query, convex hulls, and Voronoi diagrams.
Efficient splitting and merging algorithms for order decomposable problems / Grossi, R.; Italiano, G. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 154:1(1999), pp. 1-33. [10.1006/inco.1999.2811]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/199831
Citazioni
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact