✦ LIBER ✦

Steiner minimal trees in Lp2

✍ Scribed by Dietmar Cieslik; Johann Linhart

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 463 KB
Volume: 155
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00368-s

No coin nor oath required. For personal study only.

✦ Synopsis

For a finite set of points in a metric space a Steiner Minimal Tree (SMT) is a shortest tree which interconnects these points. We also consider a relative of this problem allowing at most k additional points in the tree (k-SMT), where k is a given number. We intend to discuss these problems for all planes with p-norm, i.e. the affine plane with norm II (tl, t2)II p = (I tx I ~ + I t2 IP) 1/p for 1 ~< p < oo and Ij(tl,t2)lt~ = max{Itll, It21}. We give a survey of results for the combinatorial structure of SMT and k-SMT and show the consequences for the methods to construct such trees.

📜 SIMILAR VOLUMES

On Steiner minimal trees withLpdistance

✍ Zi -Cheng Liu; Ding -Zhu Du 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 453 KB

Minimal Steiner Trees for 2k×2kSquare La

Minimal Steiner Trees for 2k×2kSquare Lattices

✍ M. Brazil; T. Cole; J.H. Rubinstein; D.A. Thomas; J.F. Weng; N.C. Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 417 KB

We prove a conjecture of Chung, Graham, and Gardner (Math. Mag. 62 (1989), 83 96), giving the form of the minimal Steiner trees for the set of points comprising the vertices of a 2 k \_2 k square lattice. Each full component of these minimal trees is the minimal Steiner tree for the four vertices of

Steiner minimal trees for regular polygo

Steiner minimal trees for regular polygons

✍ D. Z. Du; F. K. Hwang; J. F. Weng 📂 Article 📅 1987 🏛 Springer 🌐 English ⚖ 755 KB

Absorbing Angles, Steiner Minimal Trees,

Absorbing Angles, Steiner Minimal Trees, and

✍ H. Martini; K. J. Swanepoel; P. Oloff de Wet 📂 Article 📅 2009 🏛 Springer 🌐 English ⚖ 328 KB

Steiner Minimal Trees in Rectilinear and

Steiner Minimal Trees in Rectilinear and Octilinear Planes

✍ Song Pu Shang; Tong Jing 📂 Article 📅 2007 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 299 KB

Full Minimal Steiner Trees on Lattice Se

Full Minimal Steiner Trees on Lattice Sets

✍ M. Brazil; J.H. Rubinstein; D.A. Thomas; J.F. Weng; N.C. Wormald 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 497 KB

Given a finite set of points P in the Euclidean plane, the Steiner problem asks us to constuct a shortest possible network interconnecting P. Such a network is known as a minimal Steiner tree. The Steiner problem is an intrinsically difficult one, having been shown to be NP-hard [7]; however, it oft