| 摘 要： | A Steiner minimal tree (SMT) for a set of points P in the plane is a shortest networkinterconnecting P.The construction of a SMT for a general set P is known to be an NP-completeproblem.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 calledmild bar wave.We show that a SMT for a mild bar wave must assume a special form,thus the numberof trees needed to be inspected is greatly reduced.Furthermore if a mild bar wave is also a mild rectan-gular wave,then we produce a Steiner tree constructible in linear time whose length can exceed thatof a SMT by an amount bounded by the difference in heights of the two endpoints of the rectangularwave,thus independent of the number of points.When a rectangular wave satisfies some otherconditions (including ladders as special cases),then the Steiner tree we produced is indeed a SMT.
|
