Minimal Steiner Trees for Rectangular Arrays of Lattice Points

✍ Scribed by M Brazil; J.H Rubinstein; D.A Thomas; J.F Weng; N.C Wormald

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 619 KB
• Volume: 79
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1996.2751

✦ Synopsis

We construct minimal Steiner trees for any square or rectangular array of integer lattice points on the Euclidean plane.

1997 Academic Press

1. INTRODUCTION AND PRELIMINARIES

This paper answers a series of questions raised by Chung et al. in [3] on the length of the shortest network interconnecting a square or rectangular array of integer lattice points on the Euclidean plane. Such a network must clearly be a tree, and is known as a minimal Steiner tree. Minimal Steiner trees differ from minimal spanning trees in that they may contain vertices other than the initial given points. The original points being interconnected are usually referred to as terminals and the extra vertices as Steiner points. An example of a minimal Steiner tree, denoted X, for the vertices of a unit square is shown in Figure 1. A comprehensive discussion of minimal Steiner trees can be found in [5].