Steiner minimal trees for bar waves (Q580349)

A Steiner minimal tree (SMT) for a set of points P in the plane is a shortest network interconnecting P. The construction of an SMT for a general set P is known to be an NP-complete problem. Recently, SMTs have been constructed for special sets P such as ladders, splitting trees, zigzag lines and co-circular points. In this paper we study SMTs for a wide class of point-sets called mild bar wave. We show that an SMT for a mild bar wave must assume a special form, thus the number of trees needed to be inspected is greatly reduced. Furthermore if a mild bar wave is also a mild rectangular wave, then we produce a Steiner tree constructible in linear time whose length can exceed that of an SMT by an amount bounded by the difference in heights of the two endpoints of the rectangular wave, thus independent of the number of points. When a rectangular wave satisfies some other conditions (including ladders as special cases), then the Steiner tree we produced is indeed an SMT.