Premium
The local Steiner problem in normed planes
Author(s) -
Swanepoel Konrad J.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<104::aid-net5>3.0.co;2-k
Subject(s) - steiner tree problem , mathematics , combinatorics , degree (music) , vertex (graph theory) , unit sphere , affine transformation , ball (mathematics) , point (geometry) , discrete mathematics , graph , pure mathematics , geometry , acoustics , physics
We present a geometric analysis of the local structure of vertices in a Steiner minimum tree in an arbitrary normed plane in terms of so‐called absorbing and critical angles, thereby unifying various results known for specific norms. We find necessary and sufficient conditions for a set of segments emanating from a point to be the neighborhood of a vertex in a Steiner minimum tree. As corollaries, we show that the maximum possible degree of a Steiner point and of a given point are equal, and equal 3 or 4, except if the unit ball is an affine regular hexagon, where it is known that the maximum degree of a Steiner point is 4 and of a regular point is 6. We also characterize the planes where the maximum degree is 4, the so‐called X‐planes , and present examples. In particular, if the unit ball is an affine regular 2 n ‐gon, Steiner points of degree 4 exist if and only if n = 2, 3, 4, or 6. © 2000 John Wiley & Sons, Inc.