Efficient heuristics for orientation metric and Euclidean Steiner tree problems (Q1977863)

In the Steiner minimum tree (SMT) problem a set \(P\) of points in the plane has to be connected by a tree containing \(P\) as subset of the nodes. In contrast to classical applications, where only horizontal and vertical connections of nodes are allowed, the authors consider connections with orientations given by angles \({i\pi \over\sigma}\), \(0\leq i\leq\sigma-1\), \(\sigma \in \mathbb{Z}\). For the resulting \(\lambda_\sigma\)-metric the \(\lambda_\sigma\)-SMT is solved to optimality for \(|P|\in\{3,4\}\). For the general \(\lambda_\sigma\) case an \(O(n^2)\) heuristic is introduced. The paper includes numerical experiments on benchmark data.