Efficient Data Structures for Range Aggregate Queries

Abstract

Computational geometry is a branch of algorithms that deals with objects that are geometric newlinein nature. In the last four decades, computational geometry has graduated into a rich area newlineencompassing matured techniques designed to deal with geometric data. Range queries are one newlineof the most widely studied topics in computational geometry and is defined as: Given a set S of newlinegeometric objects (points, lines etc), preprocess S into a data structure such that given a query newlineobject (point, circle, rectangle, square, polygon), we can efficiently report the subset S newline0 of the newlineobjects intersecting the query. Range query problems are generally data structuring problems newlinewith focus on query time and/or space-efficiency. Output sensitivity also plays an important newlinerole in the study of range query problems. Broadly speaking, output sensitive algorithm is an newlinealgorithm whose run time depends on the size of the output in addition to the size of the input. newlineThus, the run time of an output sensitive algorithm (also known as query time for range queries) newlineis expressed as T(n) = f(n) + k × g(n) where n is the number of input elements, f(n), g(n) newlineare some polynomials and k is the number of output elements to be reported. Precisely, the newlinerun time of an output sensitive algorithm is divided into two parts namely (i) the computation newlinetime which denotes the time needed to compute the results and (ii) the reporting time which newlinedenotes the time needed to report each output element. Generally, for range queries, f(n) and newlineg(n) are bounded by O(logc(1) n) and O(logc(2) n) where c(1), c(2) are constants and#8805; 0. Thus, the newlinequery time for a range query is often of the form O(logc(1) n + k logc(2) n). Most of the studies newlinein range aggregate queries attempt to reduce the value of c(2) preferably to zero. newlineIn this work, we study seven range query problems with applications in databases, geographical information systems, VLSI Electronic Design Artwork-Design Rule Checking (EDA-DRC) newlinetools. For most of the problems studied in this dissertation, we have succeeded in redu