No label defined (Q4945795)

Since any Steiner tree is an edge disjoint union of its full components, constructing full Steiner trees is of significant importance in the Steiner tree problem. Clearly, any algebraic approach of the Steiner tree problem involves a certain coordinate system. By Lemma 1.1, a coordinate system with three axes \(120^\circ\) apart, called a hexagonal coordinate system, is more natural than the common Cartesian coordinate system for constructing full Steiner trees. In Section 2 we study the use of hexagonal coordinates in the Steiner tree problem. Motivated also by Lemma 1.1, in Section 3 we define a generalization of Steiner trees, called APE-Steiner trees. Along the same line, the APE-Steiner tree problem can be solved using a general three coordinate system. In the last section, using hexagonal coordinate systems we give a direct proof of the NP-hardness of the Euclidean Steiner tree problem. For the entire collection see [Zbl 0932.00010].