AF: Small: Fundamental Problems in Geometric Data Structures

点击翻译按钮获取中文摘要

In today's era of big data, we frequently encounter large amounts of data that are geometric, or that may be represented as points or objects in geometric spaces. There is a growing need for the design of efficient data structures that can process and answer queries about such geometric data quickly. This project focuses on some of the most fundamental and central data structuring problems in computational geometry, and explores new ideas to obtain improved results on these longstanding problems. The research project will be integrated with the development of courses for undergraduate and graduate students that incorporate the latest research findings on geometric data structures.Among the fundamental problems studied are point location and nearest neighbor search. The project will also investigate geometric data structure problems in new settings that arise from modern-day applications, including distance-related problems in high dimensions, distance-related problems concerning unit-disk graphs (frequently used to model ad hoc wireless networks) and other types of geometric graphs, and streaming algorithms that can process high volumes of geometric data quickly with a limited amount of storage space.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.