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.
