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.