Carleton University - School of Computer Science Honours Project
Winter 2022
Approaching a Solution for Colored Orthogonal
Range Searching: A Static Algorithm Analysis
ABSTRACT
Orthogonal range searching is a branch of computational geometry concerned with querying a set of
data in a geometrical fashion. In orthogonal range searches, the data being queried is transformed
into a set of points on an d-dimensional plane, and an orthogonal range (ex/ 4x6 rectangle) is chosen
for which we want data to be returned. In this paper we examine a variety of algorithms and data
structures used for solving range query problems. We then describe a specific data structure used to
store and query a single-side bounded range query on colored points. This query returns the number
of unique colored points contained above or below a query line in O(log^2(n) + k) time, where k is the
number of unique points reported. The data structure uses O(n k^(1/3)log n) storage, where k is the
number of points reported.