This slot is focused on the Rectilinear Steiner Minimum Tree (RSMT) problem:
Problem
Given a set P of n points, find a set S of Steiner points such that the Minimum Spanning Tree (MST) over P + S has minimum cost.
The RSMT problem is NP-hard. This page presents an exact algorithm (GeoSteiner), two quadratic heuristics (BOI and BI1S), a O(nlog2n) heuristic (batched greedy), and a O(n log n) Rectilinear Minimum Spanning Tree (RMST) code. The RMST is never more than 50% longer than RSMT, and on the average comes within 12% of the RSMT. The BI1S, BOI, and batched greedy heuristics come on the average within 0.5-0.7% of the optimum RSMT.