Hexagonal coordinate systems and Steiner minimal trees (Q1080858)

A Steiner minimal tree for n points in the plane is a tree of minimal length whose vertices include the original n points. Added vertices (other than the original n points) are called Steiner points. It is well- known that Steiner points are degree-3 vertices with each pair of edges meeting at a \(120^ o\) angle. In a full Steiner tree, every edge is incident to at least one Steiner point (any Steiner minimal tree can be decomposed into a union of full Steiner trees). Thus in a full Steiner tree, all edges have one of three directions (each \(120^ o\) apart). The authors develop the idea of using a hexagonal coordinate system - with three axes \(120^ o\) apart - rather than the standard Cartesian coordinates, for analyzing Steiner trees. This has the potential of giving an algebraic rather than geometric structure to the problem. The authors use their approach to give a more efficient construction of a Steiner tree with a given topology than Melzak's method.