AF: Small: Fundamental Problems in Geometric Data Structures

AF：小：几何数据结构中的基本问题

• 批准号: 1814026
• 负责人: Timothy Chan
• 金额: $ 50万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814026&HistoricalAwards=false
• 关键词: AF; Small; Fundamental; Problems; Geometric

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.

在当今的大数据时代，我们经常遇到大量几何数据，或者可能表示为几何空间中的点或对象的数据。人们越来越需要设计能够快速处理和回答有关此类几何数据的查询的高效数据结构。该项目重点关注计算几何中一些最基本和最核心的数据结构问题，并探索新的想法以获得这些长期存在的问题的改进结果。该研究项目将与本科生和研究生课程的开发相结合，融合几何数据结构的最新研究成果。研究的基本问题包括点定位和最近邻搜索。该项目还将研究现代应用中出现的新设置中的几何数据结构问题，包括高维中与距离相关的问题、有关单位圆盘图（经常用于建模自组织无线网络）的距离相关问题以及其他该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique

动态广义最近对：重温 Eppstein 的技术

• DOI: 10.1137/1.9781611976014.6
• 发表时间: 2020-01
• 期刊: Proc. SIAM Symposium on Simplicity of Algorithms (SOSA
• 作者: Chan; Timothy M.
• 通讯作者: Timothy M.

Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

全单调矩阵选择的近最优随机算法

• DOI: 10.1137/1.9781611976465.89
• 发表时间: 2021-01-01
• 作者: Timothy M. Chan

Approximate shortest paths and distance oracles in weighted unit-disk graphs

加权单位圆盘图中的近似最短路径和距离预言

• DOI: 10.20382/jocg.v10i2
• 发表时间: 2019-01
• 期刊: Journal of computational geometry
• 作者: Chan, Timothy M.;Skrepetos, Dimitrios
• 通讯作者: Skrepetos, Dimitrios

On Locality-Sensitive Orderings and Their Applications

关于局部敏感排序及其应用

• DOI: 10.1137/19m1246493
• 发表时间: 2020-01
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Chan, Timothy M.;Har;Jones, Mitchell
• 通讯作者: Jones, Mitchell

Dynamic Colored Orthogonal Range Searching

动态彩色正交范围搜索

• DOI: 10.4230/lipics.esa.2021.28
• 发表时间: 2024-09-13
• 作者: Timothy M. Chan;Zhengcheng Huang
• 通讯作者: Zhengcheng Huang