Let P be a set of n points on the euclidean plane. Let Ls(P) and Lm(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree on P, respectively. In 1968, Gilbert and Pollak conjectured that for any P, Ls(P) >/= (radical3/2)Lm(P). We provide an abridged proof for their conjecture in this paper.
No takes yet. Share an insight, caveat, or question.
Du et al. (1990) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: