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

几何扳手起源于经典图论，是计算几何中引人入胜的数学结构，在机器人、计算机网络和分布式系统等计算领域有许多应用。扳手也可以在城市规划、交通网络设计和许多其他需要高效网络设计的领域中找到应用。在过去的几十年里，出现了大量新的几何扳手构造算法和大量的结构结果。尽管如此巨大的工作，几何扳手的理论和实践之间仍然存在差距。研究者和一组学生研究人员将致力于通过算法工程和实验来缩小这一差距。一个重要的扳手构建算法集合将被设计和实验使用大量的点集（合成和现实世界），以确定他们的实际效果。该项目的合作研究活动将为参与的学生，主要是本科生，为未来几何计算的理论和实践做好准备。这些算法的工程和实验将成为这些学生处理算法效率实际问题的独特学习经验。该项目的科学成果将用于创建算法工程和实验的新课程材料，学生将在其中应用计算机算法的理论知识。该计划将推行两项具体的推广措施：(i)为本地高中生举办暑期编程营，以及（ii）组织高中编程比赛。我们强烈鼓励少数族裔和代表性不足的学生加入这项研究。几何扳手主要对几何学者有理论意义。理论方法的主要局限是缺乏专一性。铅笔和纸的几何扳手构造算法与工作程序相去甚远，需要付出相当大的努力来填充从前者到后者的细节。如果没有工程和实验，这些最先进的算法可能永远局限在理论领域。在这个项目中，几何扳手构造算法将被视为实验室科目，类似于自然科学，与传统的理论分析有很大不同。这可能会在该领域开辟新的方向。在大数据时代，几何数据集非常丰富，并且正在以前所未有的速度生成。没有严格和系统的实验，仍然不知道这些构建算法中的哪一个是实用的，特别是对于大量的点集（有数百万个点）。新的实用启发式的设计将在生成的扳手的速度、内存和质量方面提高它们的实际性能。对这些算法的重新关注将为它们在大量点集的实际应用提供新的见解，否则这些算法无法从理论分析中获得。并行适应实用算法（将通过严格和系统的实验来确定）和设计新的可证明有效的实用混合算法将在这个大数据时代有益。将获得理论分析来支持实验观察，这将提供一个整体的观点，他们的实际表现。在即将进行的算法实验中有可能获得新的理论结果。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.