Carleton University - School of Computer Science Honours Project
Winter 2022
Approaching a Solution for Colored Orthogonal Range Searching: A Static Algorithm Analysis
Thomas Hayes
SCS Honours Project Image
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.