The Steiner ratio for points on a triangular lattice

The Steiner ratio for points on a triangular lattice

0.00 Avg rating0 Votes
Article ID: iaor200962797
Country: South Africa
Volume: 24
Issue: 2
Start Page Number: 185
End Page Number: 193
Publication Date: Jul 2008
Journal: ORiON
Authors:
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’.

Reviews

Required fields are marked *. Your email address will not be published.