NSF-BSF:AF:Small:Algorithmic Tools for Proximity Problems among Curves

NSF-BSF:AF:Small：曲线间邻近问题的算法工具

• 批准号: 2008551
• 负责人: Boris Aronov
• 金额: $ 39.91万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008551&HistoricalAwards=false
• 关键词: NSF; BSF; AF; Small; Algorithmic

In recent years, a vast volume of path and trajectory data has become available. The data comes from a variety of sources, as different as motion capture of actors, flight paths of birds, bus routes, taxi trips, sports analysis, GPS sensors on cattle, and stock-performance recordings. Recent advancements of technology, such as the proliferation of GPS-enabled mobile phones, makes such data sources ubiquitous. This gives rise to several challenges, such as storing the data, identifying and removing redundancies, clustering it, and preprocessing it to facilitate a variety of common and useful queries.Consequently, the world is witnessing an outburst of research surrounding path and trajectory data. Much of it is experimental, with little focus on the guaranteed performance, in terms of time, storage, and quality, of the various heuristics used for processing the sea of information. In this project, the team of researchers is designing effective algorithms and data structures with provable performance guarantees for fundamental problems dealing with path and trajectory data. They are concentrating their attention on proximity problems, including nearest-neighbor searching, clustering, and related questions. However, in contrast with much of the previous related research, the team intends to put special emphasis on the usefulness of the obtained results, by taking into account properties that are often found in real-life inputs. They are also considering these problems in the streaming model, which often suits the circumstances in practice. (In this model one assumes that the overall volume of information is overwhelmingly large, that the data arrives in small frequent updates, and that limited amounts of time and memory are available to handle each update.) The team is developing new methods and combine them with existing ones to attack challenging algorithmic questions in processing of massive amounts of curve and trajectory data in various settings. The methodology is intended to be applicable to other problems in computational geometry and beyond. The researchers are designing algorithms that are applicable to real-life problems of relevance to the academia, industry, and society. Moreover, proximity problems for path and trajectory data are especially suitable for introducing high-school and university students to the world of algorithms, as the background needed for understanding the problems themselves is minimal and nice ideas at various levels of sophistication can be presented through easily accessible illustrations.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.

近年来，大量的路径和轨迹数据已经可用。 这些数据来自多种来源，包括演员的动作捕捉、鸟类的飞行路径、公交车路线、出租车行程、运动分析、牛身上的 GPS 传感器以及股票表现记录。 最近的技术进步，例如支持 GPS 的移动电话的普及，使得此类数据源无处不在。 这带来了一些挑战，例如存储数据、识别和删除冗余、对其进行聚类以及对其进行预处理以方便各种常见且有用的查询。因此，世界正在见证围绕路径和轨迹数据的研究的爆发。 其中大部分都是实验性的，很少关注用于处理海量信息的各种启发式方法在时间、存储和质量方面的性能保证。 在这个项目中，研究人员团队正在设计有效的算法和数据结构，并为处理路径和轨迹数据的基本问题提供可证明的性能保证。 他们将注意力集中在邻近问题上，包括最近邻搜索、聚类和相关问题。 然而，与之前的许多相关研究相比，该团队打算通过考虑现实生活输入中经常发现的属性，特别强调所获得结果的有用性。 他们也在流模型中考虑这些问题，这通常适合实践中的情况。 （在此模型中，假设信息总量极大，数据以小而频繁的更新方式到达，并且可用于处理每次更新的时间和内存有限。）该团队正在开发新方法并将其与现有方法相结合，以解决在各种设置下处理大量曲线和轨迹数据时遇到的具有挑战性的算法问题。 该方法旨在适用于计算几何及其他领域的其他问题。 研究人员正在设计适用于与学术界、工业界和社会相关的现实生活问题的算法。 此外，路径和轨迹数据的邻近问题特别适合向高中生和大学生介绍算法世界，因为理解问题本身所需的背景很少，并且可以通过易于理解的插图呈现各种复杂程度的好想法。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A General Technique for Searching in Implicit Sets via Function Inversion

通过函数求逆搜索隐式集合的通用技术

• 发表时间: 2024
• 期刊: SIAM
• 作者: Aronov, Boris;Cardinal, Jean;Dallant, Justin;Iacono, John
• 通讯作者: Iacono, John

Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

动态近似乘法加权最近邻

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Aronov, Boris;Katz, Matthew J.
• 通讯作者: Katz, Matthew J.

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

• DOI: 10.48550/arxiv.2203.10241
• 发表时间: 2022-03
• 作者: P. Agarwal;B. Aronov;Esther Ezra;M. J. Katz;M. Sharir

Time and space efficient collinearity indexing

• DOI: 10.1016/j.comgeo.2022.101963
• 发表时间: 2022-11
• 期刊: Comput. Geom.
• 作者: B. Aronov;Esther Ezra;M. Sharir;Guy Zigdon

Computing in Geometry and Topology

几何和拓扑计算

• DOI: 10.57717/cgt.v2i1.14
• 发表时间: 2023
• 期刊: Computing in Geometry and Topology
• 作者: Aronov, Boris;Basit, Abdul;de Berg, Mark;Gudmundsson, Joachim
• 通讯作者: Gudmundsson, Joachim