General Information

---

Project Description

We are interested in understanding Steiner trees for configurations of points in Euclidean spaces of arbitrary dimensions. Research in this area has been done for points on the plane, but our knowledge is very limited regarding higher dimensions. A natural object to study is the regular simplex, and for this, we have a conjectured topology of the Steiner minimal tree for regular simplexes. Our aim in this project is to extend our knowledge of Steiner minimal trees for the regular simplex in arbitrary dimensions as well as explore ways to construct it.

Research Log

Week 1 (6/5-6/9)

I started by getting familiar with the notions, terminology and main results involving our topic of research, as well as preparing a presentation introducing the project to the whole REU2023 group. I also met with my supervisor as well as the other member of my research group to establish a work plan and determine which notions from the literature are the most important ones for us to focus on and understand.

Week 2 (6/12-6/16)

In this week, we perused the literature (specifically [1] and [2]) and proved a lower bound for the distance between two connected Steiner points in a Euclidean space of arbitrary dimensions. Also, we focused on generalizing the properties of Steiner trees in the Euclidean plane for Euclidena spaces of arbitrary dimensions. Finally, as part of the REU2023 program, I attended a seminar by Dimitris Metaxas on "Scalable and Explainable AI Analytics for Computer Vision and Medical Applications".

Week 3 (6/19-6/23)

In this week, we met with Karthik in New York and had the opportunity to experience the working life in this city. We implemented an algorithm previously presented in [3] to find the optimal Steiner trees for the regular simplex in Euclidean space of dimensions 3-11 and discovered that our conjectured topology is the topology of these optimal trees.

Week 4 (6/26-6/30)

In this week, I focused on finding a graph theoretical property that would describe our topology and that indicates why our conjectured topology is that of the optimal Steiner tree for regular simplexes. We came up with a notion we named as All Paths Tree Cost of a given tree T (abbreviated as APTC(T)) and described as the sum of the pairwise instances between the leaves of the tree. We plan on exploring further if this property is suficient to describe our topology as optimal. Also, we received a visit from the New York REU23 program participants.

Week 5 (7/3-7/7)

In this week, we worked on determining whether our conjectured topology is optimal by trying to prove that any given tree on n terminals can undergo a series of transformations that decrease its APTC and obtain a tree isomorphic to our conjectured topology. Also, we had the opportunity to celebrate 4th of July in the US!

Week 6 (7/10-7/14)

In this week, we started writing the report for the end of the REU and also attempted to prove the optimality of our construction for minimal Steiner trees for regular simplexes with 2^k vertices.

Week 7 (7/17-7/21)

In the final week, we presented our findings to the rest of the REU students and agreed to compile our results in the report. We headed back to Prague at the end of the week.

Project Summary

References

• [1]  Chung, F. R. K., and Gilbert, E. N. "Steiner trees for the regular simplex." Bull. Inst. Math. Acad. Sinica 4.2 (1976): 313-325.
• [2]  Gilbert, E. N., and Pollak, H. O. "Steiner Minimal Trees." SIAM Journal on Applied Mathematics 16.1, (1968): 1-29.
• [3]  Smith, W.D. "How to find Steiner minimal trees in euclidean d-space". Algorithmica 7 (1992): 137-177 .

Acknowledgements

This work was carried out while the author G.A. Gamboa Quintero was a participant in the 2023 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.