Steiner minimal trees with one polygonal obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle omega in the Euclidean plane. We assume omega touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k. If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T. Given a full primitive topology along with omega convex, we prove that T can be determined in O(n² + n log2(k)) time. Further, if omega is nonconvex, we then show that O(n² + nk log k) time is required.