Item

Abstract

Orthogonal range searches arise in many areas of application, most often, in
database queries. Many techniques have been developed for this problem and
related geometric search problems where the points are replaced by general
objects like simplices, discs etc. This report is a brief study of some of the
techniques developed and how they can be plugged together to give various
solutions for this problem. The motivation for this study was to find a general
method to solve this problem in time O(log n) and space O (npolylog n) where
the dependency on the dimension affects only the constant in the query time and
the polylogarithmic factor in the space complexity. The study hasn't led to any
such algorithm so far but it helps us to see the common thread in some of the
structures and tools available in the study of algorithms. Interestingly, some
of these structures and tools were proposed for quite other purposes than
answering Orthogonal Range Queries. A small part of the thesis also deals with
Dominance Queries because of their close relation to the Orthogonal Range
Queries in terms of both problem definition and solution.