Biased Range Trees

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal decision tree for S and D. The memory and preprocessing requirements of the data structure are O(n log n).

Keywords

Computational Geometry, Data Structures and Algorithms, I.3.5

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/163067

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0806.2707
 http://arxiv.org/abs/0806.2707

Collections

arXiv