AF:Small: Fundamental Geometric Data Structures

存储和查询大数据量的有效方法在大多数计算机应用程序中扮演着至关重要的角色。在许多情况下，存储的数据和查询都可以表示为几何对象，例如点、线和矩形。这一场景传统上是在计算几何学中研究的。然而，几何数据结构在计算机科学的其他领域有许多应用，从空间数据库到地理信息系统，从计算机图形学到生物信息学。这个项目将研究几何数据结构及其与理论计算机科学其他领域的联系。研究人员和他的学生还将学习所获得的算法的实现及其潜在的应用。这个项目将集中在基本的几何数据结构问题上：正交范围搜索问题，点定位问题，最近邻问题，和动态凸壳问题。尽管经过了几十年的广泛研究，但与这些问题相关的几个重要的开放问题仍然存在。本项目旨在扩展和深化这一领域的知识：减少或消除上下界之间的差距，调查不同计算模型中问题的相对复杂性，并找到更有效的方法来动态化静态数据结构。研究人员还将探索几何数据结构和外部存储器模型中的算法之间的联系，使该项目的贡献适用于更大类别的应用程序。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Efficient methods of storing and querying large data volumes play a crucial role in a majority of computer applications. In many situations, both the stored data and the queries can be represented as geometric objects, such as points, lines, and rectangles. This scenario is traditionally studied in computational geometry. However, geometric data structures have numerous applications in other areas of Computer Science, from spatial databases to geographic information systems, from computer graphics to bioinformatics. This project will study geometric data structures and their connections with other areas of theoretical Computer Science. The investigator and his students will also study the implementations of obtained algorithms and their potential applications. This project will focus on fundamental geometric data structuring problems: the orthogonal range searching problem, the point location problem, the nearest neighbor problem, and the dynamic convex hull problem. Despite several decades of extensive study, there are still several important open questions related to these problems.This project aims to extend and deepen the knowledge of this area: reduce or eliminate the gaps between the lower and upper bounds, investigate the relative complexities of problems in different models of computation, and find more efficient ways to dynamize the static data structures. The investigator will also explore the connections between geometric data structures and algorithms in the external memory model, making the project's contributions applicable to a larger class of applications.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.