Given a finite set of points S in a metric space, an interconnection network is a collection of paths in which it is possible to start at any point of S and travel to any other point in S. A Steiner tree is an interconnection network of minimum total length, where the minimum is taken over all possible interconnection networks. Steiner trees in Euclidean space (equipped with the l_2 metric) are structurally completely characterized and simultaneously very difficult to compute in practice---NP-hard, in fact. The same is true when Euclidean space is equipped with the l_1 metric. In this talk, we will explore the elegant geometry of Steiner trees in the l_1 and l_2 metrics, see a linear time reconstruction algorithm, and discuss open problems.
Zoom Link: https://washington.zoom.us/j/92849568892