You are here

1-2-3 Seminar: Euclidean Steiner Trees

Joe Rogge, University of Washington
Friday, March 1, 2024 - 2:30pm to 3:30pm
PDL C-401

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:

Event Type: 
Event Subcalendar: