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.