CRII: AF: RUI: Engineering and Experiments with Geometric Spanner Construction Algorithms for Massive Point Sets

CRII：AF：RUI：大规模点集的几何扳手构造算法的工程和实验

• 批准号: 1947887
• 负责人: Anirban Ghosh
• 金额: $ 17.49万
• 依托单位: University of North Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-05-01 至 2023-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1947887&HistoricalAwards=false
• 关键词: CRII; AF; RUI; Engineering; Experiments

Geometric spanners, having their roots in classic graph theory, are fascinating mathematical structures in computational geometry with numerous applications in computing such as robotics, computer networks, and distributed systems. Spanners also find applications in urban planning, transport network design, and in many other areas where efficient network design is a necessity. The last few decades saw a plethora of new geometric-spanner construction algorithms and a multitude of structural results. Despite such monumental work, there remains a gap between theory and practice of geometric spanners. The investigator and a team of student researchers will aim to narrow down this gap through algorithm engineering and experiments. An important collection of spanner construction algorithms will be engineered and experimented using massive point sets (synthetic and real-world) to determine their practical efficacy. The collaborative research activities in this project will prepare the participating students, primarily undergraduates, for the future of theory and practice of geometric computing. Engineering and experiments with such algorithms will serve as a unique learning experience for these students to deal with practical issues of algorithmic efficiency. The scientific outcomes of this project will be leveraged to create new course material on algorithm engineering and experiments, where students will apply their theoretical knowledge of computer algorithms to practice. This project will implement two specific initiatives for outreach: (i) organization of summer coding camps for local high school students, and (ii) organization of high-school programming competition. Minority and underrepresented students will be highly encouraged to join this research.Geometric spanners are mainly of theoretical interest to geometers. The main limitation of the theoretical approach is the lack of specificity. A pencil-and-paper geometric-spanner construction algorithm is a far cry from a working program, and considerable effort is required to fill in the details to get from the former to the latter. Without engineering and experiments, these state-of-the-art algorithms may remain confined forever in the theoretical arena. In this project, the geometric spanner construction algorithms will be treated as laboratory subjects, akin to natural sciences and much different from traditional theoretical analysis. This will likely open up new directions in the field. In the era of Big Data, geometric datasets are abundant and are being generated at an unprecedented rate. Without rigorous and systematic experimentation, it remains unknown which of these construction algorithms are practical, especially for massive point sets (having millions of points). The design of new practical heuristics will increase their real-world performance, in terms of speed, memory, and quality of the generated spanners. A renewed focus on these algorithms will provide new insights regarding their practical uses for massive point sets, which otherwise cannot be obtained from their theoretical analyses. Parallel adaptations of the practical algorithms (to be determined using rigorous and systematic experiments) and the design of new provably efficient practical hybrid algorithms will be beneficial in this age of Big Data. Theoretical analyses will be obtained to support the experimental observations, which will provide a holistic view of their practical performance. New theoretical results are likely to be obtained from the algorithm experiments to be conducted.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.

几何空间起源于经典图论，是计算几何中令人着迷的数学结构，在机器人、计算机网络和分布式系统等计算领域有着广泛的应用。Spanner还可以应用于城市规划，交通网络设计以及许多其他需要高效网络设计的领域。 在过去的几十年里，出现了大量的新的几何构造算法和大量的结构结果。尽管有这样的不朽的工作，仍然有理论和实践之间的差距几何空间。研究人员和一组学生研究人员将通过算法工程和实验缩小这一差距。 将使用大量点集（合成和真实世界）设计和实验一系列重要的并行构建算法，以确定其实际功效。 在这个项目中的合作研究活动将准备参与的学生，主要是本科生，几何计算的理论和实践的未来。这些算法的工程和实验将成为这些学生处理算法效率实际问题的独特学习体验。该项目的科学成果将被用来创建算法工程和实验的新课程材料，学生将把他们的计算机算法理论知识应用于实践。该项目将实施两项具体的外联举措：（一）为当地高中学生组织暑期编码夏令营;（二）组织高中编程竞赛。少数民族和少数民族的学生将被高度鼓励参加这项研究。几何空间主要是理论感兴趣的几何学家。 理论方法的主要局限是缺乏具体性。 一个纸和纸的几何图形构造算法与一个工作程序相差甚远，从前者到后者需要相当大的努力来填充细节。如果没有工程和实验，这些最先进的算法可能永远局限于理论竞技场。 在这个项目中，几何图形的构造算法将被视为实验对象，类似于自然科学，与传统的理论分析有很大不同。这可能会在该领域开辟新的方向。在大数据时代，几何数据集非常丰富，并且正在以前所未有的速度生成。 如果没有严格和系统的实验，仍然不知道这些构造算法中哪些是实用的，特别是对于大规模的点集（具有数百万个点）。 新的实用算法的设计将在速度、内存和生成的spatial质量方面提高其真实世界的性能。 对这些算法的重新关注将为它们在大规模点集上的实际应用提供新的见解，否则无法从它们的理论分析中获得。在这个大数据时代，并行调整实用算法（将通过严格和系统的实验来确定）和设计新的可证明有效的实用混合算法将是有益的。将获得理论分析，以支持实验观察，这将提供一个整体的看法，他们的实际表现。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Bounded-Degree Plane Geometric Spanners in Practice

有界度平面几何扳手的实践

• DOI: 10.1145/3582497
• 发表时间: 2023
• 期刊: ACM Journal of Experimental Algorithmics
• 作者: Anderson, Frederick;Ghosh, Anirban;Graham, Matthew;Mougeot, Lucas;Wisnosky, David
• 通讯作者: Wisnosky, David

Minimalist Coverage and Energy-Aware Tour Planning for a Mobile Robot

移动机器人的极简覆盖范围和能源感知行程规划

• DOI: 10.1109/case49997.2022.9926546
• 发表时间: 2022
• 期刊: 2022 IEEE 18th International Conference on Automation Science and Engineering (CASE
• 作者: Ghosh, Anirban;Dutta, Ayan;Sotolongo, Brian
• 通讯作者: Sotolongo, Brian

Experiments with unit disk cover algorithms for covering massive pointsets

用于覆盖海量点集的单位圆盘覆盖算法的实验

• DOI: 10.1016/j.comgeo.2022.101925
• 发表时间: 2023
• 期刊: Computational Geometry
• 作者: Friederich, Rachel;Ghosh, Anirban;Graham, Matthew;Hicks, Brian;Shevchenko, Ronald
• 通讯作者: Shevchenko, Ronald

Visualizing WSPDs and their applications

可视化 WSPD 及其应用

• 发表时间: 2022
• 期刊: International Symposium on Computational Geometry
• 作者: Ghosh A.;Shariful F.;Wisnosky D.
• 通讯作者: Wisnosky D.

Sparse hop spanners for unit disk graphs

单位圆盘图的稀疏跳扳手

• DOI: 10.1016/j.comgeo.2021.101808
• 发表时间: 2022
• 期刊: Computational Geometry
• 作者: Dumitrescu, Adrian;Ghosh, Anirban;Tóth, Csaba D.
• 通讯作者: Tóth, Csaba D.