Data Structures for Range Closest Pair Queries

The objective of this project is to construct optimal data structures for the range closest pair (RCP) problem. The RCP problem aims to construct a data structure such that whenever a specific query range is given, the closest point-pair among those inside the given range can be reported efficiently. The RCP problem has been studied in variant versions depending on the type of a query range, which includes quadrants, trips, rectangles, and half-planes. Despite of the significant interest for the RCP problem, some variants remain open waiting for optimal solutions. For example, the best-known solutions of the RCP problem for rectangle and strip query ranges are not optimal. In the age of large information, the importance of the RCP problem is increasing in the sense that it is the fundamental algorithm to find a required data efficiently from an enormous dataset, especially focusing on a specific range of our interest.

Faculty Supervisor:

Michiel Smid

Student:

Partner:

Pohang University of Science and Technology

Discipline:

Computer science

Sector:

Information and Communications Technology; Artificial Intelligence

University:

Carleton University

Program: