ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract LetS = {A, B, C, D} consist of the four corner points of a convex quadrilateral where diagonals [A, C] and [B, D] intersect at the pointO. There are two possible full Steiner trees forS, theAB-CD tree hasA andB adjacent to one Steiner point, andC andD to another; theAD-BC tree hasA andD adjacent to one Steiner point, andB andC to another. Pollak proved that if both full Steiner trees exist, then theAB-CD (AD-BC) tree is the Steiner minimal tree if AOD〉3 (〈) 90°, and both are Steiner minimal trees if AOD=90°. While the theorem has been crucially used in obtaining results on Steiner minimal trees in general, its applicability is sometimes restricted because of the condition that both full Steiner trees must exist. In this paper we remove this obstacle by showing: (i) Necessary and sufficient conditions for the existence of either full Steiner tree forS. (ii) If AOD≥90°, then theAB-CD tree is the SMT even if theAD-BC tree does not exist. (iii) If AOD〈90° but theAD-BC tree does not exist, then theAB-CD tree cannot be ruled out as a Steiner minimal tree, though under certain broad conditions it can.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187892
Permalink
