Biased Range Trees

Simple item page
dc.creatorDujmovic, Vida
dc.creatorHowat, John
dc.creatorMorin, Pat
dc.date2008-06-17
dc.date.accessioned2026-07-07T09:45:00Z
dc.date.available2026-07-07T09:45:00Z
dc.descriptionA 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).
dc.identifierhttps://arxiv.org/abs/0806.2707
dc.identifierhttp://arxiv.org/abs/0806.2707
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163067
dc.subjectComputational Geometry
dc.subjectData Structures and Algorithms
dc.subjectI.3.5
dc.titleBiased Range Trees
dc.typetext

Files

Collections

arXiv