The Steiner ratio for points on a triangular lattice

Abstract

The study of spanning trees and Steiner trees arises naturally in applications, such as in the design of integrated circuit boards, communication networks, power networks and pipelines of minimum cost. In such applications the Steiner ratio is an indication of how badly a minimum spanning tree performs compared to a Steiner minimal tree. In this paper a short proof is presented for the Steiner ratio for points on a triangular lattice in the Euclidean plane. A Steiner tree in two dimensions is \\lifted\" to become a rectilinear tree in three dimensions, where it is altered. The rectilinear tree is then projected back into the plane and the result readily follows. A short note at the end of the paper compares our three-dimensional rectilinear trees to \"impossible objects\" such as Escher\'s \\Waterfall.\"

Keywords: Spanning tree, Steiner tree, Steiner ratio, rectilinear Steiner tree, hexagonal Steiner tree, equilateral triangular lattice, Escher.

ORiON Vol. 24 (2) 2008: pp. 185-193