Steiner minimal trees for three points with one convex polygonal obstacle (Q1179763)

The authors consider the problem of constructing Steiner minimal trees for three points in the Euclidean plane in the presence of a single polygonal obstacle. Without the obstacle this is one of the classical problems in mathematics (Fermat problem). In the paper an \(O(n)\) algorithm for solving the problem is presented, where \(n\) is the number of extreme points of the obstacle. After a preprocessing step for the obstable (which however requires \(O(n)\) time) the complexity of the algorithm applied to the processed obstacle is reduced to \(O(\log n)\) time. The reader of this paper must have the willingness to go through a rather involved system of denotations in order to follow the arguments. This effort may be worthwhile since the special case of three points may be a building block for the case of more than three nodes (in the same way as this occurs for the problem without obstacles).