Steiner minimal trees for a class of zigzag lines (Q1186798)

A Steiner tree is the shortest network interconnecting a given set \(A\) of points in the Euclidean plane, with the introduction of additional points allowed. This paper generalizes results of \textit{D. Z. Du}, \textit{F. K. Hwang}, \textit{G. D. Song} and \textit{G. Y. Ting} [Discrete Comput. Geom. 2, 401-414 (1987; Zbl 0623.05013)] to a less restrictive class of zigzag lines --- a broken line which turns alternatively right and left at given vertices \(a_ 1\), \(a_ 2,\dots,a_ m\). The zigzag line is normal if the lengths of the straight line segments are increasing (in a technically defined way). The set \(A\) is Steiner convex if all points of \(A\) are vertices of its Steiner polygon. This paper gives the structure of Steiner trees for the class of normal, Steiner convex zigzag lines. It is shown that the Steiner ratio conjecture holds for such trees and an \(O(n^ 2)\) algorithm is available to find Steiner trees for this class of zigzag lines.