AF:Small: Fundamental Geometric Data Structures

AF:Small：基本几何数据结构

• 批准号: 2203278
• 负责人: Yakov Nekrich
• 金额: $ 59.41万
• 依托单位: Michigan Technological University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2203278&HistoricalAwards=false
• 关键词: AF; Small; Fundamental; Geometric; Data

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.

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